answer4.md

Question 4 (Optional)

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).

Answer A - Brute Force

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)

[Preferred] Answer B - Sorted Array

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)

Test Cases

Code is at Repl.it

Conclude

With the same space complexity, answer B (sorted array) has lower time complexity and therefore is preferred.