Pell numbers are numbers that are similar to the Fibonacci numbers and are generated by below formula
P_{n} = 2*P_{n-1} + P_{n-2}
with seeds P_{0} = 0 and P_{1} = 1
Your task is to print Nth pell number.
 
Example 1:
Input:
N = 3
Output:
5
Explanation:
P_{0} = 0, P_{1} = 1, P_{2} = 2*1+0 = 2,
P_{3} = 2*2+1 = 5
Example 2:
Input:
N = 4
Output:
12
Explanation:
P_{0} = 0, P_{1} = 1, P_{2} = 2*1+0 = 2,
P_{3} = 2*2+1 = 5, P_{4} = 2*5+2 = 12
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function getNthPell() which takes an Integer N as input and returns the answer modulo (10^{9}+7).
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def getNthPell(self, N):

        # code here

Solutions:
class Solution:

	def getNthPell(self, N):
		if N == 0:
			return 0
		elif N == 1:
			return 1
		else:
			(a, b, m) = (0, 1, int(1000000000.0) + 7)
			for i in range(N - 1):
				c = (2 * b + a) % m
				a = b
				b = c
			return b


class Solution:

	def getNthPell(self, N):
		(p0, p1) = (0, 1)
		for i in range(N):
			(p0, p1) = (p1, (2 * p1 + p0) % 1000000007)
		return p0


class Solution:

	def getNthPell(self, N):
		if N <= 1:
			return N
		a = 0
		b = 1
		for i in range(2, N + 1):
			c = 2 * b + a
			a = b
			b = c
			b = b % 1000000007
		return b


class Solution:

	def getNthPell(self, N):
		arr = [0] * (N + 1)
		arr[0] = 0
		arr[1] = 1
		for i in range(2, N + 1):
			arr[i] = (2 * arr[i - 1] + arr[i - 2]) % 1000000007
		return arr[N]


class Solution:

	def getNthPell(self, N):
		fab = [0, 1]
		for j in range(2, N + 1):
			v = (fab[1] * 2 % (10 ** 9 + 7) + fab[0]) % (10 ** 9 + 7)
			(fab[0], fab[1]) = (fab[1], v)
		return fab[1]


class Solution:

	def getNthPell(self, N):
		f = [0, 1]
		for i in range(2, N + 2):
			f.append((f[i - 1] * 2 + f[i - 2]) % (10 ** 9 + 7))
		return f[N]


class Solution:

	def getNthPell(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		lst = [0, 1]
		for i in range(2, N + 1):
			val = (2 * lst[i - 1] + lst[i - 2]) % 1000000007
			lst.append(val)
		return lst[N]