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:

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

That's all. Thanks for reading!