CareerCup

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

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

Should use pascals triange to solve this. Not iteration.

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?

there is a formula given in Coremen to find 'i'th element of fibonacci series
F(i) = ((1 + √(5) / 2)^i) / √(5) + 0.5

long no1 =0, no2 =1
for (int i= 3;i<=500;i++ {
	long newNow = no1 + no2;
	no1 = no2;
	no2 = newNow;
}

fun(int n)
{
if(n==0)
return 0;
else if (n==1)
return 1;
else
return (fun(n-1)+fun(n-2));
}

void main
{
int n1,n2,n3,i=2;

{
n1=0;
n2=1;
printf("%d\n%d",n1,n2);
while(2<=5000)
{ n3=n2+n1;
printf("%d\n",n3);
n1=n2;
n2=n3;
i++;
}
}

Generate Fibonacci numbers iteratively. Select the 5000th number.