Fibonacci Number
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

Question

Fibonacci Number

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

Accepted Answer

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:

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.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(logn)Explanation:

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)).

Java (SE 1.8)

/*



	Time complexity: O(log(N)) 

	Space complexity: O(1)

	

	where 'N' is the given number.



*/



public class Solution 

{

	public static boolean CheckFiboNum(int n) 

    {

		// Check if the number is equal to 0 or 1 then return true.

		if (n == 0 || n == 1) 

        {

			return true;

		}



		// Variables to store the previous Fibonacci Numbers.

		long a = 0, b = 1;



		while (true) 

        {

			// Variable to store the next Fibonacci Number.

			long add = a + b;



			// if next Fibonacci number is equal to given number then return true.

			if (add == n) 

            {

				return true;

			}

			

            // If next Fibonacci number is greater than the given number then stops the iteration.

			else if (add > n) 

            {

				break;

			}



			// Change 'b' to 'a' and 'a' to next Fibonacci Number.

			b = a;

			a = add;

		}



		// If the given number is not a Fibonacci Number then return false.

		return false;

	}

}

Python (3.5)

'''

	Time complexity: O(log(N)) 

	Space complexity: O(1)

	

	where ‘N’ is the given number.

'''



def CheckFiboNum(n):



    #  Check if the number is equal to 0 or 1 then return true.

    if (n == 0 or n == 1):

        return True



    #  Variables to store the previous Fibonacci Numbers.

    a = 0

    b = 1



    while (True):



        #  Variable to store the next Fibonacci Number.

        add = a + b



        #  if next Fibonacci number is equal to given number then return true.

        if (add == n):

            return True



        #  If next Fibonacci number is greater than the given number then stops the iteration.

        elif (add > n):

            break



        #  Change 'b' to 'a' and 'a' to next Fibonacci Number.

        b = a

        a = add



    #  If the given number is not a Fibonacci Number then return false.

    return False

C++ (g++ 5.4)

/*



	Time complexity: O(log(N)) 

	Space complexity: O(1)

	

	where 'N' is the given number.



*/



bool CheckFiboNum(int n)

{

    //  Check if the number is equal to 0 or 1 then return true.

    if (n == 0 || n == 1)

    {

        return true;

    }



    //  Variables to store the previous Fibonacci Numbers.

    int a = 0, b = 1;



    while (true)

    {

        //  Variable to store the next Fibonacci Number.

        long long add = a + b;



        //  if next Fibonacci number is equal to given number then return true.

        if (add == n)

        {

            return true;

        }

        

        //  If next Fibonacci number is greater than the given number then stops the iteration.

        else if (add > n)

        {

            break;

        }



        //  Change 'b' to 'a' and 'a' to next Fibonacci Number.

        b = a;

        a = add;

    }



    //  If the given number is not a Fibonacci Number then return false.

    return false;

}

Accepted Answer

Mathematics

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