CareerCup

Here is a hint:

Represent Fibonacci numbers in matrix form:
(F[n+1], F[n]
F[n], F[n-1])
= A^n, where
A =
((1,1),
(1,0))

Perform fast exponential (repeated squaring) to compute A^n.

c# implementation.
O(logn) time.
O(1) space.

namespace FibonacciInLogNTime {

    static class Program {

        // time complexity O(log n)
        static private long Fib( long n ) {
            n--;
            long[,] res = { { 1, 0 }, { 0, 1 } }; // Identity matrix (with ones on the main diagonal and zeros elsewhere)
            long[,]  a  = { { 1, 1 }, { 1, 0 } }; // Identity matrix for Fibonacci seq { { F(n+1), F(n) }, { F(n), F(n-1) } }

            while ( n > 0 ) {
                if ( ( n & 1 ) == 1 ) {
                    res = res.Multiply( a );
                }
                n /= 2;
                a = a.Multiply( a );
            }
            return res[ 0, 0 ];
        }

        private static long[,] Multiply ( this long[,] arrA, long[,] arrB ) {
            return new [,] { {
                    ( arrA[ 0, 0 ] * arrB[ 0, 0 ] + arrA[ 0, 1 ] * arrB[ 1, 0 ] ), // [0,0]
                    ( arrA[ 0, 0 ] * arrB[ 0, 1 ] + arrA[ 0, 1 ] * arrB[ 1, 1 ] )  // [0,1]
                },{
                    ( arrA[ 1, 0 ] * arrB[ 0, 0 ] + arrA[ 1, 1 ] * arrB[ 1, 0 ] ), // [1,0]
                    ( arrA[ 1, 0 ] * arrB[ 0, 1 ] + arrA[ 1, 1 ] * arrB[ 1, 1 ] )  // [1,1]
                }
            };
        }

        static void Main( string[] args ) {
            var res = Fib( 5 );
        }
    }
}

why no answers? after the hint it is quite simple.

Use dynamic programming.
Store the previous fib numbers in an array
and access then at the next fib call

#include<stdio.h>
#include<stdlib.h>
#include <string.h>

int  check=1,temp =0;
int * array;
int fabonacii(int n)
{
	if(check)
	{
		check=0;
		array = (int *) malloc(sizeof(int) * (n+1));
		memset(array,0,sizeof(int) * (n+1));
	}
	
	if (n==1)
	{
		array[n]=0;
    	return 0;	
	}
	else if (n==2)
	{
		array[n]=1;
    	return 1;	
	}
	else
	{
		if(array[n] !=0)
		return (array[n]);
		else
		{
			temp=fabonacii(n-2) + fabonacii(n-1);
			array[n]=temp;
			return temp;
		}
	}

}

int main(void)
{    
    printf("%d",fabonacii(100));
	free(array);
	return 0;
}

Fn = 1/sqrt(5) * pow(2,-n) * (pow(1+sqrt(5),n) - pow(1-sqrt(5),n))

Fn = 1/sqrt(5) * (1/2^n) * ( (1+sqrt(5))^n - (1-sqrt(5))^n)