Skip to content

Instantly share code, notes, and snippets.

@john012343210
Created November 10, 2018 16:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save john012343210/095e6739b74eef50c4d73b21d944835f to your computer and use it in GitHub Desktop.
Save john012343210/095e6739b74eef50c4d73b21d944835f to your computer and use it in GitHub Desktop.
calculate the nearest fibonacci numbers for each element in array with O(n) with n being the size of input
from math import sqrt,log,ceil
def fibo(n):
return int((((1+sqrt(5))**n)-((1-sqrt(5))**n))/((2**n)*sqrt(5)))
def nearestFibo(array):
for k in array:
larger_Nearest_Fibo = ceil( (log(sqrt(5)*k)) /(log((1+sqrt(5))/2)) )
print(fibo(larger_Nearest_Fibo))
nearestFibo([75024,600000]) # output is 75025 and 832040
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment