1. Nth Fibonacci
Python
## O(2^n) time | O(N) space
def getNthFib(n):
# Write your code here.
if n == 1:
return 0
elif n == 2:
return 1
else:
return getNthFib(n-1) + getNthFib(n-2)
## O(N) time | O(N) space
def getNthFib(n, memrize = {1:0, 2:1}):
# Write your code here.
if n in memrize:
return memrize[n]
else:
memrize[n] = getNthFib(n-1, memrize) + getNthFib(n-2, memrize)
return memrize[n]
## O(n) time | O(1) space
def getNthFib(n):
next_ = [0, 1]
counter = 3
while (counter <= n ):
sum_ = next_[0] + next_[1]
next_[0] = next_[1]
next_[1] = sum_
cunter += 1
return next_[1] if n>=2 else next_[0]
2. Produc Sum
Python
## O(N) time where N is the total number of elements of the original arrays and its sub-arrays and so on and so forth
## O(D) space where D is the depth of the sub-arrays
# Tip: You can use the type(element) function to check whether an item
# is a list or an integer.
def productSum(array, multiplier = 1):
# Write your code here.
sum_ = 0
for element in array:
if type(element) is list:
sum_ += productSum(element, multiplier+1)
else:
sum_ += element
return sum_ * multiplier
