How to check if the given number is a Fibonacci number?
A Fibonacci series starts with 0, 1. Remaining elements are formed by adding previous two numbers.
Here are a few Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…
If a number is given, a straight forward way to check if it is a Fibonacci number is to generate the numbers one by one until we get the required number or greater than that.
Here is the python code do that.
One more approach is based on a property of Fibonacci numbers.
If 5*x2+4 or 5*x2-4 (or both) is a perfect square, we can conclude that it is a Fibonacci number.
The C++ code is given below.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cmath> | |
| #include <cstdio> | |
| #include <vector> | |
| #include <iostream> | |
| #include <algorithm> | |
| using namespace std; | |
| int main() { | |
| int t; | |
| cin >> t; | |
| while( t-- ) | |
| { | |
| long long n; | |
| cin >> n; | |
| double root = sqrt(5.0*n*n+4.0); | |
| long long iRoot = root; | |
| if( root == iRoot ) | |
| { | |
| cout << "IsFibo" << endl; | |
| } | |
| else | |
| { | |
| root = sqrt(5.0*n*n-4.0); | |
| iRoot = root; | |
| if( root == iRoot ) | |
| { | |
| cout << "IsFibo" << endl; | |
| } | |
| else | |
| { | |
| cout << "IsNotFibo" << endl; | |
| } | |
| } | |
| } | |
| return 0; | |
| } |
by