Write a function that takes an array of integers as input. For each integer, output the next fibonacci number. Solution
that work both cpu and memory efficient are appreciated.
Fibonacci number of Fn is defined by:
Fn = Fn-1 + Fn-2
F1 = 1, F2 = 1
For example:
nextFibonacci([1,22,9])
Output:
2
34
13
Explanation: 2 is the next fibonacci number great than 1. The fibonacci number after 9 is 13, and after 22 is 34.
Below sections show 2 possible solutions, A and B (preferred).
Time Complexity O(n^2)
Space Complexity: O(n)
# Assume an array with num >= 0 only
def nextFibonacci(arr):
ans = []
for item in arr:
if item == 0:
ans.append(1)
continue
elif item == 1:
ans.append(2)
continue
else:
last = 1
secondLast = 1
while last <= item:
tmp = last + secondLast
secondLast = last
last = tmp
ans.append(last)
return ans
Time Complexity:
O(n items) * O(largest no. of fibo items traversed before the number is found)
= O(n^2)
Space Complexity: O(n)
Time Complexity O(nlog(n))
Space Complexity O(n)
# Assume an array with num >= 0 only
def nextFibonacci(arr):
descending = sorted(arr, reverse=True)
last = 1
secondLast = 1
ansMap = {}
while(len(descending) > 0):
item = descending[-1]
if item == 0:
ansMap[descending.pop()] = 1
elif item == 1:
ansMap[descending.pop()] = 2
else:
if last > item:
ansMap[descending.pop()] = last
else:
tmp = last + secondLast
secondLast = last
last = tmp
return [ansMap[item] for item in arr]
Time Complexity
= sorting time + while loop + map to return the answer
= O(nlog(n)) + O(no. of items transversed in fibo series) + O(no. of items in input arr)
= O(nlog(n)) + O(n) + O(n)
= O(nlog(n)) (# Taking the most significant factor)
Space Complexity
O(n)
Code is at Repl.it
With the same space complexity, answer B (sorted array) has lower time complexity and therefore is preferred.