CareerCup

The most efficient way is iterative, only keeping the last two numbers in the sequence.

def getNthFibonacci(i):
   prev1 = 1
   prev2 = 1

   if i == 1:
      return prev1
   if i == 2:
      return prev2

   for _ in range(i - 2):
      current = prev1 + prev2

      # Push prev2 back to prev1, and add our latest one to the
      # end of the 'sequence'.
      prev2 = prev1
      prev1 = current

   return prev1

long fiboo(long int n )
{
long int pre1=0,pre2=1;
if(n==1)
return 0;
if(n==1)
return 1;

for(long int i=2;i<=n;i++)
{
long int temp=pre2
pre2=pre2+pre1;
pre1=temp;
}

return pre2;
}

better not to use recursive method , it will take a long time !
my solution resembles the above two but it has a plus point that,, for multiple inputs at the same time u just have to print those array elements;

int main()
{	long int a[1000000];
	long int n;
	a[0]=0;
	a[1]=1;
	for(i=2;i<;1000000;i++)
	{	a[i]=a[i-1]+a[i-2];
	}
	cin>>n; //the number of which fib is required;
	cout<<a[n];
return 0;
}

Can you try the 2x2 Matrix Multiplication code of Fibonnaci Series.
Its O(Log n)

There is a closed form expression for the n-th Fibonacci number.

Just iterate! time complexity is O(n). It is as simple as this:

long getNthFibonacci(long i){
	long n=1;
	long numN=1;
	long numNLess1=0;
	long temp;
	while (i!=n){
		n++;
		temp=numN+numNLess1;
		numNLess1=numN;
		numN=temp;
	}
	return numN;
}

Python O(logN) version.

This uses some recursive properties of the Fibonacci numbers to compute an individual number in logN time. It's the most efficient solution that I know of that doesn't use floats. It's all integer multiplication and addition.

def fib(n):
    if n == 0:
        return 0
    return fib2(n)[1]

def fib2(n):
    # returns (fib(n-1), fib(n)
    if n < 5:
        return tuple([0,1,1,2,3,5][n-1:n+1])
    x, y = fib2(n / 2)
    a = x*x + y*y
    b = (2*x+y)*y
    if n % 2 == 1:
        a, b = (b, a+b)
    return (a, b)

for i in range(20):
    print fib(i)

f(nth) = floor((1+sqrt(5))/2)^n / sqrt(5) +0.5)

(1 1) pow n=( fibo(n+1) fibo(n) )
(1 0) ( fibo(n) fibo(n-1) )
These are 2X2 matrices. This s the most efficient way to find fibonacci nos.

f(nth) = floor((1+sqrt(5))/2)^n / sqrt(5) +0.5)

Here is the problem written in Ruby:

def fib(nth)
  fib1 = 1
  fib2 = 1
  counter = 2
  fibonacci = [fib1, fib2]
  until counter == nth do
    fibonacci << fib = fib1 + fib2
    fib1=fib2
    fib2=fib
    counter += 1
  end
  fibonacci
end

print fib(4)

- Alex M.

Use DP