C++ Program for How to check if a given number is Fibonacci number?
Given a number ‘n’, how to check if n is a Fibonacci number. First few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ..
Examples :
Input : 8 Output : Yes Input : 34 Output : Yes Input : 41 Output : No
Following is an interesting property about Fibonacci numbers that can also be used to check if a given number is Fibonacci or not.
A number is Fibonacci if and only if one or both of (5*n2 + 4) or (5*n2 – 4) is a perfect square (Source: Wiki).
CPP
// C++ program to check if x is a perfect square #include <iostream> #include <math.h> using namespace std; // A utility function that returns true if x is perfect square bool isPerfectSquare( int x) { int s = sqrt (x); return (s * s == x); } // Returns true if n is a Fibonacci Number, else false bool isFibonacci( int n) { // n is Fibonacci if one of 5*n*n + 4 or 5*n*n - 4 or both // is a perfect square return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4); } // A utility function to test above functions int main() { for ( int i = 1; i <= 10; i++) isFibonacci(i) ? cout << i << " is a Fibonacci Number \n" : cout << i << " is a not Fibonacci Number \n"; return 0; } |
Output:
1 is a Fibonacci Number 2 is a Fibonacci Number 3 is a Fibonacci Number 4 is a not Fibonacci Number 5 is a Fibonacci Number 6 is a not Fibonacci Number 7 is a not Fibonacci Number 8 is a Fibonacci Number 9 is a not Fibonacci Number 10 is a not Fibonacci Number
Time complexity: O(logn)
As sqrt() function takes O(logn) time.
Auxiliary space: O(1)
As constant extra space is used.
Please refer complete article on How to check if a given number is Fibonacci number? for more details!