|
|
|
Interview Question: Checking if a number is fibonacci
by
Kamal Rawat
on
Jan 12, 2012
How will you check if a number is a Fibonacci number or not (Fibonacci numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21 ... )
|
|
|
|
Comments: 0 Views: 760
|
|
|
|
MCN Professionals | Interview Question of the day MCN Professionals is starting Industrial Training for MCA-2012 Batch. Have a look at our Industrial Training Program and Course Details.
-----------------------------------------------------------------------------------------------------------------------------------------
Today's Question:
By definition first 2 Fibonacci numbers are defined as 0 and 1. nth Fibonacci number can be computed as sum of (n-2)th & (n-1)th Fibonacci numbers
Fn = Fn-1 + Fn-2
Hence the Fibonacci numbers are as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
A number is given to you, how will you check if that number is a Fibonacci number or not ?
Solution:
History of Fibonacci Numbers (reference, wiki..):
Indians can feel proud that The Fibonacci sequence first appeared in Indian mathematics, in connection with Sanskrit prosody.
In the Sanskrit oral tradition, there was much emphasis on how long (L) syllables mix with the short (S), and counting the different patterns of L and S within a given fixed length results in the Fibonacci numbers; the number of patterns that are m short syllables long is the Fibonacci number Fm + 1.
Susantha Goonatilake writes that the development of the Fibonacci sequence "is attributed in part to Pingala (200 BC), later being associated with Virahanka (c. 700 AD), Gopala (c.1135 AD), and Hemachandra (c.1150)". Parmanand Singh cites Pingala's cryptic formula misrau cha ("the two are mixed") and cites scholars who interpret it in context as saying that the cases for m beats (Fm+1) is obtained by adding a [S] to Fm cases and [L] to the Fm-1 cases. He dates Pingala before 450 BCE. However, the clearest exposition of the series arises in the work of Virahanka (c. 700AD), whose own work is lost, but is available in a quotation by Gopala. In the West, the Fibonacci sequence first appears in the book Liber Abaci (1202) by Leonardo of Pisa, also known as Fibonacci. And as it is with most of the other stuff, the numbers are named after Fibonacci and called Fibonacci numbers.
Computing Fibonacci Number:
First 2 Fibonacci numbers are fixed as 0 & 1. As given in the Question, You can compute the nth Fibonacci number using (n-1)th & (n-2)th fibonacci numbers:
Fn = Fn-1 + Fn-2
These numbers also comes in shallow diagonal of Pascal triangle: see this picture.
Finding if a number is Fibonacci number or not:
One way to check if a number is Fibonacci is to keep finding Fibonacci numbers till we get a number greater than or equal to. For example, to check if a number 'n' is Fibonacci or not:
int checkfibonacci(int n)
{
int a = 0;
int b = 1;
if (n==a || n==b) return true;
int c = a+b;
while(c<n)
{
if(c == n) return true;
a = b;
b = c;
c = a + b;
}
return false;
}
Another method (Quick one) to check if a number if Fibonacci number or not, is as below:
N is a Fibonacci number if and only if ( 5*N2 + 4 ) or ( 5*N2 - 4 ) is a perfect square!
For Example:
3 is a Fibonacci number since (5*3*3 + 4) is 49 which is 7*7
5 is a Fibonacci number since (5*5*5 - 4) is 121 which is 11*11
4 is not a Fibonacci number since neither (5*4*4 + 4) = 84 nor (5*4*4 - 4) = 76 are perfect squares.
---------------------------------------------------------------------------
Interview Questions Archive:
To see all the questions in the category click
here...
|
|
|
|
|