smallest fibonacci number larger than any given number

How can we find smallest fibonacci number larger than any given number(may be upto 10^15)??
Please someone help…

You can precompute all the fibonacci number and store them in array( as the max limit is 10^15). then you can search the array.

1 Like

If you see the closed form expression of Fibonacci number, you’ll see that it grows exponentially. So there would be O(log(n)) many iteration to find smallest Fibonacci number larger than n. Here is a simple Python snippet, solved for n=10^18 in 0.02 seconds

a=1  
b=1

n=int(raw_input())

while b<=n:
    (a,b)=(b,a+b)

print b
2 Likes

thanks for the help!

//