1. Overview
The algorithm to check whether a number is a part of the Fibonacci series is helpful in various domains, such as finance, cryptography, mathematical modeling, etc.
In this tutorial, we’ll learn different ways in Kotlin to check whether a number is Fibonacci.
2. What Is Fibonacci Series?
The Fibonacci series is a well-known mathematical sequence of numbers where we represent each number as the sum of the previous two numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
We must note that we start the series with 0 and 1.
Great! We now understand the concept of the Fibonacci series clearly. So, let’s get started!
3. Using Iteration
In this section, we’ll take an iterative approach by writing the checkIfFibonacciUsingIteration() function to check if a number, n, is part of the Fibonacci series.
First, let’s initialize the first and second variables as the first two members of the series, namely, 0 and 1:
var first = 0
var second = 1
Now, we can proceed to write a while loop for calculating the next Fibonacci number iteratively:
while (first < n) {
val temp = first
first = second
second = temp + second
}
It’s worth noting that after each iteration, first takes the value of second, and second takes the value of the next Fibonacci number. Further, we can terminate the loop once first reaches the value of n.
Further, we can say that n is part of the Fibonacci series only if first and n are equal:
return n == first
Finally, let’s test the checkIfFibonacciUsingIteration() function for a few sample numbers:
assertTrue(checkIfFibonacciUsingIteration(13))
assertFalse(checkIfFibonacciUsingIteration(14))
Perfect! It works as expected.
4. Using Recursion
Alternatively, we can take a recursive approach as well.
Let’s go ahead and *write the getNthFibonacci() function to get the nth number in the Fibonacci series*:
fun getNthFibonacci(n: Int, cache: HashMap<Int, Int>): Int {
if (n == 0) return 0
if (n == 1) return 1
cache[n]?.let {
return it
}
val result = getNthFibonacci(n - 1, cache) + getNthFibonacci(n - 2, cache)
cache[n] = result
return result
}
We must note that we’ve used a cache to get us the next Fibonacci number efficiently. Further, we always find the result in the cache, and we compute the result only in case of a cache miss.
Now, we can write the checkIfFibonacciUsingRecursion() function to determine if the number, num is a Fibonacci number or not:
fun checkIfFibonacciUsingRecursion(num: Int): Boolean {
var n = 0
var cache: HashMap<Int, Int> = HashMap<Int, Int>()
while (getNthFibonacci(n, cache) <= num) {
if (getNthFibonacci(n, cache) == num) return true
n++
}
return false
}
We must note that we started with n=0 and an empty cache to calculate the Fibonacci series iteratively. If we’re about to go beyond the value of num, then we stop calculating the next Fibonacci number. Otherwise, we can infer the result based on whether or not num is the same as the most recent Fibonacci number.
Lastly, let’s verify our recursion-based approach with a positive and negative scenario:
assertTrue(checkIfFibonacciUsingRecursion(8))
assertFalse(checkIfFibonacciUsingRecursion(25))
Great! It looks like we got this one right.
5. Using Perfect Square Property
Fibonacci numbers have a unique mathematic property. If we take any number x, it will be a Fibonacci number if and only if 5x2+4 or 5x2-4 is a perfect square. So, we can use this interesting property to solve our use case.
We can start by writing the isPerfectSequare() function to check if x is a perfect square or not:
fun isPerfectSquare(x: Int): Boolean {
val s = Math.sqrt(x.toDouble()).toInt()
return s * s == x
}
Now, it’s pretty straightforward to write the checkIfFibonacciUsingPerfectSquareProperty() function that checks if a number, n, is a Fibonacci number:
fun checkIfFibonacciUsingPerfectSquareProperty(n: Int): Boolean {
return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4)
}
Ultimately, let’s be sure about our approach by testing it against a few sample numbers:
assertTrue(checkIfFibonacciUsingPerfectSquareProperty(13))
assertFalse(checkIfFibonacciUsingPerfectSquareProperty(19))
Fantastic! It looks like we’ve nailed this.
6. Using HashSet
In this section, we’ll use the HashSet data structure to store Fibonacci numbers till a particular threshold value.
Since HashSet is optimized for lookups, we can quickly determine if a number lesser than the current threshold is part of the Fibonacci series. On the other hand, if the number is greater than the threshold, we can regenerate the series on-demand basis and reset the threshold to a higher value.
Let’s start by initializing the currentLimit variable as the current threshold and the currentFibonacciHashSet variable as the first two numbers of the Fibonacci series:
var currentLimit = 0
var currentFibonacciHashSet: HashSet<Int> = hashSetOf(0, 1)
Further, let’s write the generateFibonacciNumberHashSet() function to use the iterative approach for generating the Fibonacci numbers lesser than a limit:
fun generateFibonacciNumberHashSet(limit: Int): HashSet<Int> {
val fibonacciNumberSet = HashSet<Int>()
var first = 0
var second = 1
while (first <= limit) {
fibonacciNumberSet.add(first)
val temp = first
first = second
second = temp + second
}
return fibonacciNumberSet
}
Moving on, we can write the checkIfFibonacciUsingHashSet() function to determine if n is a Fibonacci number:
fun checkIfFibonacciUsingHashSet(n: Int): Boolean {
if (n > currentLimit) {
currentFibonacciHashSet.addAll(generateFibonacciNumberHashSet(n))
currentLimit = n
}
return currentFibonacciHashSet.contains(n)
}
We must note that we’re only changing the currentFibonacciHashSet when we need to generate a longer series.
Lastly, we must verify our approach:
assertTrue(checkIfFibonacciUsingHashSet(233))
assertFalse(checkIfFibonacciUsingHashSet(4))
assertTrue(checkIfFibonacciUsingHashSet(13))
assertFalse(checkIfFibonacciUsingHashSet(2500))
It works as expected.
7. Conclusion
In this article, we learned how to check whether a number is part of the Fibonacci Series. Furthermore, we explored different solutions, using iterative and recursive-based approaches, perfect square property, and the HashSet data structure.
As always, the code from this article is available over on GitHub.