We consider only those Fibonacci numbers which are less than n , where we can consider fib [ 30 ] to be the upper bound as this will cross 10 ^ 5
int fib [ 30 ] ; fib [ 0 ] = 0 ; fib [ 1 ] = 1 ; for ( int i = 2 ; i < 30 ; i ++ ) fib [ i ] = fib [ i - 1 ] + fib [ i - 2 ] ;