Home//

C++ Check if a Number is Fibonacci Number

# C++ Check if a Number is Fibonacci Number Hey guys, in this tutorial, we will learn how to check if a number is a Fibonacci number in C++ using 3 methods:

## Method 1: Using the Perfect Square Formula

A number `n` is a Fibonacci number if and only if one of the following condition is true:

1. `5n^2 + 4` is a perfect square
2. `5n^2 - 4` is a perfect square

Let's implement this method in C++:

``````#include <stdc++.h>

using namespace std;

bool isPerfectSquare(int n) {
int root = sqrt(n);
return root * root == n;
}

bool isFibonacci(int n) {
return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4);
}

int main() {
int n;
cout << "Enter a number: ";
cin >> n;

if (isFibonacci(n)) {
cout << n << " is a Fibonacci number." << '\n';
} else {
cout << n << " is not a Fibonacci number." << '\n';
}

return 0;
}
``````

In this example, we define two helper functions: `isPerfectSquare` and `isFibonacci`.

• The `isPerfectSquare` function checks if a number is a perfect square by comparing the square of its square root with the original number.
• The `isFibonacci` function uses the formula mentioned above to check if a number is a Fibonacci number.

The result for this:

shell
``````Enter a number: 5
5 is a Fibonacci number.
``````

I really recommend using this formula as it is very simple and effective.

## Method 2: Generating Fibonacci Numbers

Another way to check if a number is Fibonacci is by generating Fibonacci numbers until we find a number greater than or equal to the given number. If the generated number is equal to the given number, then it is a Fibonacci number.

Let's implement this method in C++:

``````#include <stdc++.h>

using namespace std;

bool isFibonacci(int n) {
int a = 0;
int b = 1;

while (b < n) {
int temp = b;
b = a + b;
a = temp;
}

return b == n;
}

int main() {
int n;
cout << "Enter a number: ";
cin >> n;

if (isFibonacci(n)) {
cout << n << " is a Fibonacci number." << '\n';
} else {
cout << n << " is not a Fibonacci number." << '\n';
}

return 0;
}
``````

In this example, we use a `while` loop to generate the Fibonacci series until we find a number greater than or equal to the given number. At some time, if the generated number is equal to the given number, we conclude that it is a Fibonacci number.

From my perspective, this method is very inefficient when `n` is a large number, i.e. greater than 10^6. So I don't recommend using it.

## Method 3: Using a Set

The third method is similar to the previous one, that is we will generate the Fibonacci series. But this time, we will store them in a set and check if the given number is in the set or not.

Let's implement this method in C++:

``````#include <stdc++.h>

using namespace std;

bool isFibonacci(int n) {
unordered_set<int> fibonacciSet;
int a = 0;
int b = 1;

while (b <= n) {
fibonacciSet.insert(b);
int temp = b;
b = a + b;
a = temp;
}

return fibonacciSet.count(n) > 0;
}

int main() {
int n;
cout << "Enter a number: ";
cin >> n;

if (isFibonacci(n)) {
cout << n << " is a Fibonacci number." << '\n';
} else {
cout << n << " is not a Fibonacci number." << '\n';
}

return 0;
}
``````

Similarly, this method is a bit more inefficient than the previous one, as we have to define another variable to store the numbers. Again, I don't recommend using this.

## Conclusion 