Amazon Question-1

input : n(integer)

///////////////////////////////////////////////////////////////////////////////

Objective:Find the closest Fibonacci number such that i < n.Also show the time complexity.

///////////////////////////////////////////////////////////////////////////////

output :i(integer)

///////////////////////////////////////////////////////////////////////////////

Example :

Input : 10

Output : 8

Explanation :

Fib Series : 0 1 1 2 3 5 8 13 21

Input being 10 the number which is closest to 10 is 8.Hence the output is 8.

///////////////////////////////////////////////////////////////////////////////

Method 1 : (Iteration Method)

Complexity : Time Complexity : O(n) , Space Complexity: O(1)

Concept :

Fib Series is a series formed by adding the last two numbers to produce the next number

The first two numbers are fixed to be 0 and 1

the third number is 0+1 = 1

Series = 0 ,1,1

Next number = 1+1 = 2 (Addition of last two numbers ‘1’ and ‘1’)

Series = 0,1,1,2

Next number  = 2+1 = 3 (Addition of last two numbers ‘2’ and ‘1’)

Series = 0,1,1,2,3

And it goes on…

For more details visit:http://en.wikipedia.org/wiki/Fibonacci_number

…………………………………………………………………………………………………………………………………………..

Code :

1) Since we know that the first two numbers are always 0 and 1 so we store them in integer variables say ‘a’ and ‘b’ .

int a = 0;

int b=1;

2) Now we have to add them both to produce the third number,lets store it in a variable say ‘c’

int c = a+b;

3)Ok so our series for now is 0,1,1.How do i proceed to get the 4th number ?? 5th number ?? 6th number and Nth number

It can be done by replacing the value of ‘a’ with value of ‘b’ and ‘b’ value with the value of ‘c’.

That is

Initially

a=0

b=1

c=a+b=0+1 = 1

Now

a=b (Since b=1 new value of a =1)

b=c (Since c= 1 new value of b = 1)

And c=a+b =1(new value of a)+1 (new value of b) = 2 (Forth number)

Series now = 0,1,1,2.

…………………………………………………………………………………………………………………………………………..

Similarly

a=b (since b = 1 new value of a =1)

b=c (since c = 2 new value of b = 2)

c=a+b =1(new value of a)+2(new value of b) = 3

Series now  = 0,1,1,2,3

So what now for nth number ???

We use loop to find the nth number

///////////////////////////////////////////////////////////////////////////////

int a=0;

int b=1;

int c;

for(int i =2;i<=n;i++) //We start from i=2 because we already have taken a=0 and b =1 which are the first two number of fib series.

{

c=a+b;// adding them to produce the third result

a=b; //replacing value of a with a value of b

b=c; //replacing value of b with value of c

}

print c;

The following code would produce the fib of nth number say n=4 output would be 2

But our question demands to find the closest fib number given the input i such that n<i where n is the fib number and i is the input.

So we modify our code to produce the output by adding the following line to it.

if(c<n)

ans = c;

So our code would be

int a=0;

int b=1;

int c,result;

for(int i =2;i<=n;i++) //We start from i=2 because we already have taken a=0 and b =1 which are the first two number of fib series.

{

c=a+b;// adding them to produce the third result

a=b; //replacing value of a with a value of b

b=c; //replacing value of b with value of c

if(c>n)

result = c;

}

print result;

…………………………………………………………………………………………………………………………………………..

Complete C++ Code

…………………………………………………………………………………………………………………………………………..

#include<stdio.h>

int fib(int n)

{

int result=0,i,c,a=0,b=1;

for(i=2;i<n;i++)

{

c=a+b;

a=b;

b=c;

if(c<n) result=c;
}

return final;

}

int main()

{

int n=10;

printf( ” %d “, fib(n));

}

*******************************************************************************

Method 2 :

Complexity: Time:O(log n),Space : O( log n)

Concepts :

We can also find the fib number using the matrices

If the matrix

[1           1]

[1           0]

is multiplyed n times then the resultant matix is a 2×2 matix with the following values

[ n+1 th fib               nth fib]

[n th fib                     n-1th fib]

given n as the desired number to find.

Note : If we directly multiply these matrices to produce the nth fib number then it’s complexity would O(n)

So how do i make it O(log n)

Here’s the trick :

Consider the following example:

If you want to compute 3^8 = 3*3*3*3*3*3*3*3               -1 step

=9*3*3*3*3*3*3                                                                                    -2 step

=27*3*3*3*3*3                                                                                       -3 step

=81*3*3*3*3                                                                                            -4 step

=243 *3 *3*3                                                                                             -5 step

= 729*3*3                                                                                                  -6 step

= 2187*3                                                                                                    -7 step

=6561                                                                                                          -8 step

This would lead to O(n) complexity inoder to get O(log n) do this

3^8 = 3*3*3*3*3*3*3*3                           -step 1

square the resultant product of first two numbers.

3*3 = 9                                                               – step 2

Square 9

9*9 = 81                                                          -step 3

Square 81

81*81 = 6561                                           -step 4

Use this for multiplication of matrices and find the nth fib number.

Note this works for n = even but if its odd ??

Then multiply the final result witht the fib matrix [1           1]

[0            1] to produce the nth number

///////////////////////////////////////////////////////////////////////////////

int M[2][2] = {{1,0}{0,1}}

    int fib(int n)
    {
    matpow(n-1);
    return M[0][0];
    }

    void matpow(int n)
    {
    if (n > 1) {
        matpow(n/2);
        M = M*M;
    }
    if (n is odd) M = M*{{1,1}{1,0}}
    }

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s