smallest fibonacci number larger than any given number

general
,
1

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

2

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
3

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
4

thanks for the help!