## Interview Question

Developer Program Engineers**Country:**India

Hi this is written in C++ but will similarly work in Java also with few modifications....

#include <iostream>

using namespace std;

int main()

{

int t1,t2,t3,count;

t1=0;

t2=1;

count=1;

do

{

t3=t1+t2;

count++;

t1=t2;

t2=t3;

} while(count<=5000);

cout << "5000th element in fibonacci series is " << t3;

return 0;

}

5000th element in fibonacci series is 2020817954

//finding the nth fibonacci number

//Time : O(logn)

//Space O(logn)

//All we need to do is multiply {1,1},{1,0} i.e {F(n+1),F(n)},{F(n),F(n-1)} 4999 times so that we get the 5000th fibonacci number

class Fibonacci{

private static void fib(int F[][],int n){

if(n==1)

return ;

//n/2 because if we multiply {1,1,1,0} with itself it becomes 2 times and that if we multiply by itself

//it becomes 4 times and if we multiply that by {1,1,1,0} it will becomes 3 times

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

fib(F,n/2);

multiply(F,F);

if(n%2!=0)

multiply(F,M);

}

private static void multiply(int F[][],int M[][]){

int x=F[0][0]*M[0][0]+F[0][1]*M[1][0];

int y=F[0][0]*M[0][1]+F[0][1]*M[1][1];

int z=F[1][0]*M[0][0]+F[1][1]*M[1][0];

int w=F[1][0]*M[0][1]+F[1][1]*M[1][1];

F[0][0]=x;

F[0][1]=y;

F[1][0]=z;

F[1][1]=w;

}

public static void main(String args[]){

int F[][]= {{1,1},{1,0}};

int n=Integer.parseInt(args[0]);

fib(F,n-1);

System.out.println("Fib("+n+") = "+F[0][1]);

//0,1,1,2,3,5,8,13,21,34

}

}

//Input : javac career_cup.java ;java Fibonacci 9; // here 9 is the nth fibonacci number we need to find

//Output: Fib(9) = 21

You would need to use datatype like java.math.BigInteger

```
int i = 2;
BigInteger a = new BigInteger("1");
BigInteger b = new BigInteger("1");
BigInteger temp;
while (i != 5000) {
temp = b;
b = a.add(b);
a = temp;
i++;
}
System.out.println("\n" + b);
```

Ans. 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

I prepared this one with the TDD

Test Class

```
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class FibonTest {
@Test
public void return0WhenFibon0(){
assertEquals(0,Fibon.fibo(0));
}
@Test
public void return1WhenFibon1(){
assertEquals(1,Fibon.fibo(1));
}
@Test
public void return3WhenFibon2(){
assertEquals(3,Fibon.fibo(2));
}
@Test
public void return6WhenFibon3(){
assertEquals(6,Fibon.fibo(3));
}
@Test
public void return45WhenFibon9(){
assertEquals(45,Fibon.fibo(9));
}
}
```

Fibon

```
public class Fibon {
public static int fibo(int input) {
int result=0;
while(input>0){
result+=input--;
}
return result;
}
}
```

```
public class Fibonacci {
public static void main(String[] args) {
long start1 = System.currentTimeMillis();
System.out.println(fib(5000));
long end1 = System.currentTimeMillis();
System.out.println((end1-start1));
}
public static long fib(int n){
int i=0;
long memo[] = new long[n+1];
for(;i<=n;i++)
memo[i]=-1;
memo[0]=0;
memo[1]=1;
return calcFib(n, memo);
}
public static long calcFib(int n, long memo[]){
if (memo[n]!=-1)
return memo[n];
memo[n] = calcFib(n-2,memo)+calcFib(n-1,memo);
return memo[n];
}
}
```

5000th number in the series is 535601498209671957

```
package Fibonacci5000th;
import java.math.BigInteger;
public class Fibonacci5000th {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BigInteger[] fib = new BigInteger[5001];
fib[0] = new BigInteger("0");
fib[1] = new BigInteger("1");
for(int i = 2 ; i<5000 +1; i++){
fib[i] = fib[i-1].add(fib[i-2]);
}
System.out.println(fib[5000]);
}
}
```

does this give correct output?

Can be done in O(log n) without big magic (by matrix multiplication method) or in constatn time with a lot of math magic (search for Binet's Formula) :)

- tpcz May 23, 2014