Geek just learned about Fibonacci numbers. 
The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, ...
where the next number is found by adding up the two numbers before it.
He defines a new series called Geeky numbers. Here the next number is the sum of the K preceding numbers.
You are given an array of size K, GeekNum[ ], where the i^{th} element of the array represents the i^{th} Geeky number. Return its N^{th} term.
Note: This problem can be solved in O(N^{2}) time complexity but the user has to solve this in O(N). The Constraints are less because there can be integer overflow in the terms.
Example 1:
Input:
N = 6, K = 1
GeekNum[] = {4}
Output: 
4
Explanation: 
Terms are 4, 4, 4, 4, 4, 4
Example 2:
Input:
N = 5, K = 3
GeekNum[] = {0, 1, 2}
Output: 
6
Explanation: 
Terms are 0, 1, 2, 3, 6.
So the 5th term is 6
Your Task:  
You don't need to read input or print anything. Your task is to complete the function solve( ) which takes integer N, K, and an array GeekNum[] as input parameters and returns the Nth term of the Geeky series.
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
Constraints:
1 ≤ K < 30
1 ≤ N ≤ 70
K ≤ N
0 < GeekNum[ ] < 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution():

    def solve(self, N, K, GeekNum):

        #your code goes here

Solutions:
class Solution:

	def solve(self, N, K, GeekNum):
		sm = 0
		n = N
		k = K
		if N < K:
			return GeekNum[N - 1]
		prefix_sum = [0] * N
		ans = 0
		for i in range(len(GeekNum)):
			sm += GeekNum[i]
			prefix_sum[i] = GeekNum[i]
		for i in range(k, N):
			prefix_sum[i] = sm
			sm += prefix_sum[i] - prefix_sum[i - K]
		return prefix_sum[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		if N == K:
			return GeekNum[-1]
		a = GeekNum
		s = sum(a[0:K])
		a.append(s)
		for i in range(K + 1, N):
			a.append(sum(a[i - K:i]))
		return a[-1]


from collections import deque

class Solution:

	def solve(self, N, K, GeekNum):
		geeks = deque(list(GeekNum[:K]))
		current_index = 0
		answer = GeekNum[:K]
		while len(answer) != N:
			if len(geeks) == K:
				next_number = sum(geeks)
				answer.append(sum(geeks))
				geeks.popleft()
				geeks.append(next_number)
			else:
				geeks.append(GeekNum[current_index])
				answer.append(GeekNum[current_index])
			current_index += 1
		return answer[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		if K == 1:
			return GeekNum[0]
		else:
			temp = GeekNum
			while len(GeekNum) != N:
				dump = 0
				for i in range(-1, -(K + 1), -1):
					dump += temp[i]
				temp.append(dump)
			return temp[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		for i in range(N - K):
			if K == 1:
				GeekNum.append(GeekNum[0])
			else:
				GeekNum.append(GeekNum[-1] + sum(GeekNum[len(GeekNum) - K:-1]))
		return GeekNum[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		a = []
		for i in GeekNum:
			a.append
		for i in range(N - len(GeekNum)):
			GeekNum.append(sum(GeekNum[i:K + 1 + i]))
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		x = [i for i in GeekNum]
		sm = 0
		q = []
		i = 0
		for i in range(N):
			sm += x[i]
			q.append(x[i])
			if len(q) > K:
				sm -= q.pop(0)
			if len(q) == K:
				x.append(sm)
		return x[N - 1]


class Solution:

	def solve(self, N, K, nums):
		lst = []
		fsum = 0
		if N == K:
			return nums[-1]
		for i in range(K):
			fsum += nums[i]
			lst.append(nums[i])
		lst.append(fsum)
		for i in range(K, N - 1):
			fsum -= lst[i - K]
			fsum += lst[i]
			lst.append(fsum)
		return lst[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		start = 0
		if K == 1:
			return GeekNum[0]
		s = sum(GeekNum)
		for index in range(K, N):
			GeekNum.append(s)
			s += GeekNum[-1] - GeekNum[start]
			start += 1
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		i = 0
		while K != N:
			s = sum(GeekNum[i:K])
			GeekNum.append(s)
			i = i + 1
			K = K + 1
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, arr):
		presum = 0
		for i in range(K):
			presum += arr[i]
		res = arr[:K]
		for i in range(K, N):
			res.append(presum)
			presum -= res[i - K]
			presum += res[i]
		return res[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		prefix = [0 for _ in range(N)]
		prefix[0] = GeekNum[0]
		for i in range(1, K):
			prefix[i] = prefix[i - 1] + GeekNum[i]
		for i in range(K, N):
			next_num = prefix[i - 1] - prefix[i - K] + GeekNum[i - K]
			GeekNum.append(next_num)
			prefix[i] = prefix[i - 1] + next_num
		return GeekNum[-1]


from collections import deque

class Solution:

	def solve(self, N, K, GeekNum):
		deque_nums = deque(GeekNum)
		for i in range(K, N):
			new_geeky_num = sum(deque_nums)
			deque_nums.popleft()
			deque_nums.append(new_geeky_num)
		return deque_nums[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		if N == K:
			return GeekNum[-1]
		curr_sum = sum(GeekNum)
		GeekNum.append(curr_sum)
		i = K
		while i < N - 1:
			i += 1
			curr_sum = curr_sum * 2 - GeekNum.pop(0)
			GeekNum.append(curr_sum)
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		if K == 1:
			return GeekNum[0]
		(head, tail) = (0, 0)
		sums = 0
		while tail < N:
			if tail < K:
				sums += GeekNum[tail]
				tail += 1
			else:
				GeekNum.append(sums)
				sums -= GeekNum[head]
				sums += GeekNum[tail]
				head += 1
				tail += 1
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		index = 0
		sum_ = sum(GeekNum)
		for i in range(N - K):
			GeekNum.append(sum_)
			sum_ = sum_ - GeekNum[index] + GeekNum[-1]
			index += 1
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		nxt = sum(GeekNum)
		GeekNum.append(nxt)
		j = 0
		for i in range(K + 2, N + 1, 1):
			nxt = 2 * nxt - GeekNum[j]
			GeekNum.append(nxt)
			j += 1
		return GeekNum[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		geeky = [0] * N
		for i in range(K):
			geeky[i] = GeekNum[i]
		for i in range(K, N):
			geeky[i] = sum(geeky[i - K:i])
		return geeky[N - 1]


class Solution:

	def solve(self, N, K, arr):
		if len(arr) == 1:
			return arr[0]
		if K >= N:
			return arr[N - 1]
		total = sum(arr)
		j = 0
		for i in range(N - K):
			arr.append(total)
			total += total
			total -= arr[j]
			j += 1
		return arr[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		sumo = 0
		for i in GeekNum:
			sumo += i
		beg = 0
		while len(GeekNum) < N:
			GeekNum.append(sumo)
			sumo -= GeekNum[beg]
			sumo += GeekNum[-1]
			beg += 1
		return GeekNum[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		if N < K:
			return GeekNum[N - 1]
		s = 0
		arr = []
		for i in GeekNum:
			arr.append(i)
		for i in range(N):
			if i < K:
				s += arr[i]
			else:
				arr.append(s)
				s = s * 2 - arr[i - K]
		return arr[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		if N == K:
			return GeekNum[-1]
		ans = 0
		li = GeekNum
		ans = sum(GeekNum)
		li.append(ans)
		for i in range(K, N - 1):
			ans += ans - li[i - K]
			li.append(ans)
		return ans


class Solution:

	def solve(self, N, K, GeekNum):
		lt = GeekNum
		for i in range(N):
			if len(lt) == N:
				return lt.pop(N - 1)
			lt.append(sum(lt[len(lt) - K:]))
		return -1


class Solution:

	def solve(self, N, K, GeekNum):
		n = abs(len(GeekNum) - N)
		while n > 0:
			ans = 0
			arr = GeekNum[::-1]
			for i in range(K):
				ans += arr[i]
			GeekNum.append(ans)
			GeekNum.pop(0)
			n -= 1
		if len(GeekNum) == K:
			return GeekNum[-1]
		return GeekNum[-1]


class Solution:

	def solve(self, n, k, a):
		li = a.copy()
		for i in range(n - k):
			x = 0
			for j in range(k):
				x += li[i + j]
			li.append(x)
		return li[n - 1]


class Solution:

	def solve(self, n, k, GeekNum):
		a = GeekNum
		for i in range(n):
			a.append(sum(a[-k:]))
		return a[n - 1]


import numpy as np

class Solution:

	def solve(self, n, k, g):
		na = np.array(g)
		if k == 1:
			return g[0]
		s = sum(g)
		i = 1
		while k < n:
			g.append(s)
			na = np.append(na, s)
			s = sum(g) - sum(na[:i])
			k += 1
			i += 1
		return g[n - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		num = 0
		if N == K:
			return GeekNum[-1]
		while num <= N * K:

			def fibo(lst):
				sum = 0
				for i in range(-1, -1 * (K + 1), -1):
					sum += lst[i]
				return sum
			GeekNum.append(fibo(GeekNum))
			num += K
		return GeekNum[N - 1]


class Solution:

	def solve(self, n, k, GeekNum):
		l = len(GeekNum)
		for i in range(l, n, 1):
			s = 0
			for j in range(i - k, i):
				s += GeekNum[j]
			GeekNum.append(s)
		return GeekNum[n - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		lst = []
		for r in range(0, K):
			lst.append(GeekNum[r])
		p = K
		c = 0
		for j in range(K, N):
			sum = 0
			for i in range(p - 1, c - 1, -1):
				sum = sum + lst[i]
			lst.append(sum)
			p = p + 1
			c = c + 1
		l = len(lst) - 1
		return lst[l]


class Solution:

	def solve(self, N, K, GeekNum):
		arr = GeekNum
		for i in range(K, N):
			arr.append(sum(arr[i - K:]))
		return arr[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		window = GeekNum[:]
		curr_sum = sum(window)
		for i in range(K, N):
			next_term = curr_sum
			curr_sum -= window[0]
			window = window[1:] + [next_term]
			curr_sum += next_term
		return window[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		while len(GeekNum) <= N:
			S = 0
			for i in range(K):
				S += GeekNum[-1 - i]
			GeekNum.append(S)
		return GeekNum[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		if K == 1:
			return GeekNum[0]
		ans = [0] * N
		curr_sum = 0
		for i in range(0, K):
			curr_sum += GeekNum[i]
			ans[i] = GeekNum[i]
		start = 0
		for i in range(K, N):
			ans[i] = curr_sum
			curr_sum -= ans[start]
			curr_sum += ans[i]
			start += 1
		return ans[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		z = K - 1
		for i in range(K, N):
			h = i - K
			GeekNum.append(sum(GeekNum[h:z + 1]))
			z += 1
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		if K == 1:
			return GeekNum[0]
		(a, b) = (0, 1)
		l = []
		for i in range(N):
			s = 0
			for j in GeekNum[len(GeekNum) - K:len(GeekNum)]:
				s += j
			GeekNum.append(s)
		return GeekNum[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		for j in range(len(GeekNum), N):
			fn = 0
			for i in range(1, K + 1):
				fn += GeekNum[len(GeekNum) - i]
			GeekNum.append(fn)
		return GeekNum[len(GeekNum) - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		while len(GeekNum) < N:
			GeekNum.append(sum(GeekNum[-K:]))
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		for _ in range(0, N - K):
			sum = 0
			for x in range(1, K + 1):
				sum += GeekNum[-x]
			GeekNum.append(sum)
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, G):
		j = 0
		su = sum(G)
		for i in range(N - K):
			if K == 1:
				G.append(G[0])
			else:
				G.append(su)
				su = su * 2 - G[j]
				j += 1
		return G[N - 1]


class Solution:

	def seqNext(self, K, GeekNum):
		ans = 0
		for y in range(1, K + 1):
			ans += GeekNum[-y]
		GeekNum.append(ans)

	def solve(self, N, K, GeekNum):
		for i in range(N - len(GeekNum)):
			self.seqNext(K, GeekNum)
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		if K == 1 or K == N:
			return GeekNum[-1]
		val = sum(GeekNum)
		for i in range(K, N):
			GeekNum.append(val)
			val += GeekNum[i] - GeekNum[i - K]
		return GeekNum[-1]


class Solution:

	def solve(self, N, k, l):
		n = len(l)
		for i in range(n, N):
			l.append(sum(l[i - n:]))
		return l[-1]


class Solution:

	def solve(self, N, K, A):
		x = sum(A)
		for i in range(K, N):
			A.append(x)
			x += x
			x -= A[i - K]
		return A[N - 1]
71531883


class Solution:

	def solve(self, N, K, GeekNum):
		if K == 1:
			return GeekNum[-1]
		(temp, s, count) = ([], 0, 0)
		for i in range(K - 1, -1, -1):
			s += GeekNum[i]
		GeekNum.append(s)
		for i in range(K, N):
			GeekNum.append(GeekNum[-1] * 2 - GeekNum[count])
			count += 1
		return GeekNum[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		x = []
		if K == 1:
			return GeekNum[K - 1]
		if K >= N:
			return GeekNum[N - 1]
		total = sum(GeekNum)
		j = 0
		for i in range(N - K):
			GeekNum.append(total)
			total += total
			total -= GeekNum[j]
			j += 1
		return GeekNum[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		n = len(GeekNum) - 1
		if N == n + 1:
			return GeekNum[-1]
		if N < n + 1:
			return GeekNum[N - 1]
		i = n - (K - 1)
		j = n
		s = sum(GeekNum[i:j + 1])
		while n + 1 < N:
			GeekNum.append(s)
			n += 1
			s -= GeekNum[i]
			i += 1
			j += 1
			s += GeekNum[j]
		return GeekNum[-1]


import collections

class Solution:

	def solve(self, N, K, GeekNum):
		temp = collections.deque(GeekNum)
		s = sum(temp)
		if N <= K:
			return temp[N - 1]
		for i in range(N - K):
			temp.append(s)
			s -= temp.popleft()
			s += temp[-1]
		return temp[-1]


class Solution:

	def solve(self, N, K, arr):
		if N <= K:
			return arr[N - 1]
		s = sum(arr)
		i = 0
		for _ in range(N - K):
			arr.append(s)
			s += arr[-1] - arr[i]
			i += 1
		return arr[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		X = 0
		Y = K
		for i in range(N - K):
			GeekNum.append(sum(GeekNum[X:Y]))
			X += 1
			Y += 1
		return GeekNum[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		dp = [0 for i in range(N + 1)]
		fp = 0
		for i in range(K):
			dp[i] = GeekNum[i]
		dp[K] = sum(GeekNum)
		for i in range(K + 1, N + 1):
			dp[i] = dp[i - 1] + dp[i - 1] - dp[fp]
			fp += 1
		return dp[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		l = len(GeekNum)
		if N <= l:
			return GeekNum[N - 1]
		if N > l:
			sum = 0
			while l <= N:
				l = len(GeekNum)
				sum = 0
				k = K
				while l > l - k:
					sum += GeekNum[l - 1]
					l = l - 1
					k = k - 1
				GeekNum.append(sum)
				l = len(GeekNum)
			return GeekNum[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		num = GeekNum[0:K]
		for i in range(K, N):
			num.append(sum(num))
			num.pop(0)
		return num[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		if N <= K:
			return GeekNum[K - 1]
		l = GeekNum
		s = sum(l[-K:])
		while True:
			l.append(s)
			if len(l) == N:
				break
			s = s - l[-K - 1]
			s = s + l[-1]
		return l[-1]


class Solution:

	def solve(self, N, K, GeekNum):
		p = 0
		sum = 0
		for i in range(K, N):
			for j in range(p, i):
				sum += GeekNum[j]
			GeekNum.insert(i, sum)
			p += 1
			sum = 0
		return GeekNum[N - 1]


class Solution:

	def solve(self, N, K, GeekNum):
		start = 0
		end = K
		while end < N:
			a = sum(GeekNum[start:end])
			GeekNum.append(a)
			start += 1
			end += 1
		return GeekNum.pop()