Check Is Fibonacci Number

Easy
0/40
Average time to solve is 20m
profile
Contributed by
14 upvotes
Asked in companies
AmazonTwitterMakeMyTrip

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
6
Sample Output 1:
YES
NO
Explanation of sample input 1:
In the first test case, 5 is a Fibonacci number.

In the second test case, 6 is not a Fibonacci number.
Sample Input 2:
2
1
0
Sample Output 2:
YES
YES
Explanation for sample input 2:
In the first test case, 1 is a Fibonacci number.

In the second test case, 0 is a Fibonacci number.
Hint

Can you think of going through each Fibonacci number from starting?

Approaches (2)
Brute Force

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:

 

  1. Check if ‘N’ is 0 or 1, return true.
  2. Create two variables ‘a’ and ‘b’ to store the previous Fibonacci numbers and set them to 0 and 1.
  3. Now, add the previous numbers and store the result in the new variable and check if it is equal to ‘N’ then return true.
  4. Check if, this sum is greater than ‘N’ then stops the iteration and return false.
  5. Otherwise, store the above-calculated sum in ‘a’ and the value of ‘a’ in ‘b’ and back to step 3.
Time Complexity

O(log(N)), where ‘N’ is the given number.

 

We know that, nth Fibonacci number is given as [ { (sqrt(5) + 1) / 2 } ^ n ] / sqrt(5). Now, lets assume that the given number is a kth Fibonacci number or kth Fibonacci number is just greater than the ‘N’. So,

 

 [ { (sqrt(5) + 1) / 2 } ^ k ] / sqrt(5) <= N

 

If we calculate the value of k from here then we get,

 

k <= log [ (2 * sqrt(5) * n - sqrt(5) - 1) / 2 ]

 

so the overall time complexity will be O(log(N)).

Space Complexity

O(1).

 

We are not using any extra space and so, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Check Is Fibonacci Number
Full screen
Console