Created
November 10, 2018 16:07
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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