Question

Question
The Cuckoo Sequence
A Cuckoo Sequence is defined as shown.
Cuckoo[1] = 0
Cuckoo [2] = 1
Cuckoo[n] = 1*Cuckoo[n-1] + 2*Cuckoo[n-2] + 3*1, for n > 2
Given n (1 <= n <= 109), find Cuckoo[n]
Input Specification:
input1: Integer 'n'
out put ​

Answer 1

Answer:

its doesn't works for time complexcity so try for recursion

Answer 2

Answer:

from array import array

n = int(input())

cuckoo = []

cuckoo.append(0)

cuckoo.append(1)

cuckoo.append(1)

a = 1

b = 1

c = 0

for i in range (3,n+1):

   sum = a + b

   a = b

   b = sum

   cuckoo.append(sum)

ans = 0

n = n + 1

for i in range (1,n-1):

   ans = ans + (i* cuckoo[n-i])

   i = i+1

print (ans)

Explanation: