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!