## 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 *n*th 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 *5x*^{2}+4 or *5x*^{2}-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.