Last Updated: 11 Mar, 2021
Check Is Fibonacci Number
Easy
Asked in companies
You are given an integer, all you have to do is to find whether this number is a Fibonacci number or not.
Fn is said to be a Fibonacci sequence such that each number in Fn is the sum of its two preceding numbers, starting with 0 and 1.
Fn = F(n-1) + F(n-2)
fn is said to be a Fibonacci number if it is a part of the Fn/Fibonacci sequence.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain a single integer ‘N’ which denotes the given number that has to check whether it is a Fibonacci number or not.
Output Format:
For each test case, print the “YES” if the number is a Fibonacci number. Otherwise, print “NO”.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 100
0 <= N <= 100000
Where ‘T’ is the number of test cases.
Where 'N' is the given number.
Time limit: 1 sec
Approaches
The basic idea is to keep generating Fibonacci numbers until we find a number equal to the given number or the generated number becomes greater than the given number. If the generated number is equal to the given number then it means the given number is a Fibonacci number. Otherwise, it is not a Fibonacci number.
The steps are as follows:
- Check if ‘N’ is 0 or 1, return true.
- Create two variables ‘a’ and ‘b’ to store the previous Fibonacci numbers and set them to 0 and 1.
- Now, add the previous numbers and store the result in the new variable and check if it is equal to ‘N’ then return true.
- Check if, this sum is greater than ‘N’ then stops the iteration and return false.
- Otherwise, store the above-calculated sum in ‘a’ and the value of ‘a’ in ‘b’ and back to step 3.
The basic idea of this approach is to check whether (5*n*n + 4) or (5*n*n - 4) is a perfect square or not. If they are, then ‘n’ is a Fibonacci number.
Reference: https://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers
The steps are as follows:
- Store ( 5*n*n + 4 ) in ‘a’ and ( 5*n*n - 4) in ‘b’.
- Store square root of ‘a’ and ‘b’ in “aSq” and “bSq”, respectively.
- Return true if the square of “aSq” is equal to ‘a’ or the square of “bSq” is equal to ‘b’.
- Otherwise, return false.