Siddhant made a special series and named it as G.F Series. The series follows this trend  T_{n}=(T_{n-2})^{2}-(T_{n-1})  in which the first and the second term are 0 and 1 respectively. Help Siddhant to find the first N terms of the series.
Note: Print a white space (" ") after every integer and a newline character after every testcase. The generated output is white space sensitive, do not add extra spaces on unnecessary newline characters.
Example 1:
Input:
N = 3
Output:
0 1 -1
Explanation:
First-term is given as 0 and the second 
term is 1. So the T_{3} = (T_{3-2})^{2} - (T_{3-1}) 
= T_{1}^{2} - T_{2} = 0^{2} - 1 = -1
Example 2:
Input:
N = 6
Output:
0 1 -1 2 -1 5  
Explanation:
T_{1} : 0
T_{2} : 1
T_{3} : -1
T_{4} = (1)^{2} - (-1) = 2
T_{5} = (-1)^{2} - (2) = 1 - 2 = -1
T_{6} = (2)^{2} - (-1) = 4 + 1 = 5 
Your Task:  
You don't need to read input. Your task is to complete the function gfSeries() which takes an integer N as an input parameter and print first N term of the series.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
2 <= N <= 15

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Complete search

Starter code: class Solution:

    def gfSeries(self, N : int) -> None:

        # code here

        



Solutions:
class Solution:

	def gfSeries(self, N):
		dp = []
		dp.append(0)
		dp.append(1)
		for i in range(2, N):
			dp.append(dp[i - 2] ** 2 - dp[i - 1])
		print(*dp)


class Solution:

	def gfSeries(self, N: int) -> None:
		li = []
		li.append(0)
		li.append(1)
		for i in range(2, N):
			sum1 = li[i - 2] * li[i - 2] - li[i - 1]
			li.append(sum1)
		for i in li:
			print(i, end=' ')
		print()


class Solution:

	def gf_recur(self, N, Tn_2, Tn_1, m):
		Tn = Tn_2 * Tn_2 - Tn_1
		if m == N:
			print(Tn)
			return None
		else:
			print(Tn, end=' ')
			self.gf_recur(N, Tn_1, Tn, m + 1)

	def gfSeries(self, N: int) -> None:
		Tn_2 = 0
		Tn_1 = 1
		if N == 0 or N == 1:
			print(0)
		elif N == 2:
			print(0, end=' ')
			print(1, end=' ')
		elif N > 2:
			print(0, end=' ')
			print(1, end=' ')
			self.gf_recur(N, Tn_2, Tn_1, 3)


class Solution:
	cache = dict()

	def badSolution(self, n):
		if n == 1:
			return 0
		if n == 2:
			return 1
		firstPortion = self.badSolution(n - 2) ** 2
		secondPortion = self.badSolution(n - 1)
		value = firstPortion - secondPortion
		return value

	def gfSeries(self, n: int) -> None:
		for i in range(1, n + 1):
			print(self.badSolution(i), end=' ')
		print()


def recFunc(N):
	if N == 1:
		return 0
	if N == 2:
		return 1
	return pow(recFunc(N - 2), 2) - recFunc(N - 1)

class Solution:

	def gfSeries(self, N: int) -> None:
		i = 1
		while i <= N:
			print(recFunc(i), end=' ')
			i = i + 1
		print('')


class Solution:

	def gfSeries(self, N: int) -> None:

		def gf(n):
			if n <= 2:
				return n - 1
			else:
				return gf(n - 2) ** 2 - gf(n - 1)
		lis = []
		while N > 0:
			lis.append(gf(N))
			N -= 1
		print(*lis[::-1])


class Solution:

	def gfSeries(self, N: int) -> None:
		t1 = 0
		t2 = 1
		t3 = 0
		arr = [0, 1]
		for i in range(3, N + 1):
			t3 = t1 ** 2 - t2
			arr.append(t3)
			t1 = t2
			t2 = t3
		print(*arr)


class Solution:

	def gfSeries(self, N: int) -> None:

		def gf(n):
			if n <= 1:
				return n - 1
			else:
				return gf(n - 2) ** 2 - gf(n - 1)
		lis = []
		while N > 0:
			lis.append(gf(N))
			N -= 1
		for i in range(len(lis) - 1, -1, -1):
			print(lis[i], end=' ')
		print()


class Solution:

	def gfSeries(self, N: int) -> None:

		def getSeries(N, t1, t2):
			if N == 0:
				return
			t3 = t1 * t1 - t2
			print(t3, end=' ')
			t1 = t2
			t2 = t3
			getSeries(N - 1, t1, t2)
		t1 = 0
		t2 = 1
		print(t1, end=' ')
		print(t2, end=' ')
		getSeries(N - 2, t1, t2)
		print()


class Solution:

	def gfSeries(self, N: int) -> None:
		for i in range(1, N + 1):
			if i == N:
				print(self.helper(i))
				break
			print(self.helper(i), end=' ')

	def helper(self, N):
		if N == 1:
			return 0
		if N == 2:
			return 1
		return self.helper(N - 2) * self.helper(N - 2) - self.helper(N - 1)


class Solution:

	def gfSeries(self, N: int) -> None:
		N -= 2
		l = [0, 1]

		def rec(a, b, N):
			if not N:
				return
			d = a ** 2 - b
			l.append(d)
			(a, b) = (b, d)
			rec(a, b, N - 1)
		rec(0, 1, N)
		print(*l)


class Solution:

	def gfSeries(self, N: int) -> None:
		ans = [0] * N
		if N > 1:
			ans[0] = 0
		if N > 2:
			ans[1] = 1

		def rec(N):
			if N <= 2:
				return N - 1
			else:
				temp = rec(N - 2)
				temp2 = temp * temp - rec(N - 1)
				ans[N - 1] = temp2
				return temp2
		rec(N)
		print(*ans)


class Solution:

	def gfSeries(self, N: int) -> None:
		s = 3
		a = 0
		b = 1
		c = 0
		arr = [0, 1]
		while s <= N:
			c = a ** 2 - b
			a = b
			b = c
			arr.append(c)
			s = s + 1
		print(*arr)


class Solution:

	def gfHelper(self, N, arr):
		if N == 2:
			print(arr[N - 2], arr[N - 1], end=' ')
			return
		self.gfHelper(N - 1, arr)
		arr[N - 1] = arr[N - 3] ** 2 - arr[N - 2]
		print(arr[N - 1], end=' ')
		return

	def gfSeries(self, N: int) -> None:
		arr = [0] * N
		arr[:2] = [0, 1]
		self.gfHelper(N, arr)
		print()


class Solution:

	def gfSeries(self, N: int) -> None:
		a = 0
		b = 1
		c = 0
		arr = [0, 1]
		for i in range(3, N + 1):
			c = a ** 2 - b
			a = b
			b = c
			arr.append(c)
		print(*arr)


class Solution:

	def gfSeries(self, N: int) -> None:
		res_array = []
		for i in range(1, N + 1):
			if i == 1:
				res_array.append('0')
			elif i == 2:
				res_array.append('1')
			else:
				first_term = int(res_array[i - 2 - 1])
				second_term = int(res_array[i - 1 - 1])
				res_array.append(str(first_term ** 2 - second_term))
		print(' '.join(res_array))


class Solution:

	def gfSeries(self, N: int) -> None:

		def recursion(N):
			if N == 1:
				return 0
			elif N == 2:
				return 1
			else:
				return recursion(N - 2) ** 2 - recursion(N - 1)
		for i in range(1, N + 1):
			print(recursion(i), end=' ')
		print()


class Solution:

	def getGF(self, num, dp) -> int:
		if num <= 1:
			return num
		if dp[num]:
			return dp[num]
		dp[num] = self.getGF(num - 2, dp) ** 2 - self.getGF(num - 1, dp)
		return dp[num]

	def gfSeries(self, N: int) -> None:
		dp = [None] * (N + 1)
		ans = []
		for i in range(N):
			ans.append(self.getGF(i, dp))
		print(*ans)


class Solution:

	def gfSeries(self, N: int) -> None:
		l = [0, 1] + [-1] * (N - 2)
		N = N - 1

		def fun(N, l):
			if l[N] != -1:
				return l[N]
			l[N] = fun(N - 2, l) ** 2 - fun(N - 1, l)
			return l[N]
		fun(N, l)
		print(*l)


class Solution:

	def gfSeries(self, N: int) -> None:
		t = [0, 1]
		for i in range(2, N):
			tn = t[i - 2] ** 2 - t[i - 1]
			t.append(tn)
		string_of_ints = ' '.join((str(i) for i in t))
		print(string_of_ints)


class Solution:

	def gfSeries(self, N: int) -> None:
		l = [0, 1]
		for i in range(2, N):
			ln = l[i - 2] ** 2 - l[i - 1]
			l.append(ln)
		print(*l)


class Solution:

	def gfSeries(self, N: int) -> None:
		l = [0, 1]
		i = 2
		while i < N:
			x = l[i - 2] ** 2 - l[i - 1]
			l.append(x)
			i += 1
		print(*l)


class Solution:

	def gfSeries(self, N: int) -> None:
		T = [0, 1] + [0] * (N - 2)
		for i in range(2, N):
			T[i] = T[i - 2] ** 2 - T[i - 1]
		print(*T)


class Solution:

	def solve(self, N):
		if N == 1:
			return 0
		if N == 2:
			return 1
		j = self.solve(N - 2)
		k = self.solve(N - 1)
		ans = j * j - k
		return ans

	def gfSeries(self, N: int) -> None:
		for i in range(1, N + 1):
			if i == N:
				res = self.solve(i)
				print(res)
				break
			res = self.solve(i)
			print(res, end=' ')
		return


class Solution:

	def getSeries(self, lst, n, t1, t2):
		if n == 0:
			return lst
		T = t1 ** 2 - t2
		lst.append(T)
		self.getSeries(lst, n - 1, t2, T)
		return lst

	def gfSeries(self, N: int) -> None:
		arr = [0, 1]
		x = self.getSeries(arr, N - 2, 0, 1)
		print(*x)


class Solution:

	def gfSeries(self, N: int) -> None:
		for i in range(1, N + 1):
			print(self.T1(i), end=' ')
		print()

	def T1(self, n):
		if n == 1:
			return 0
		elif n == 2:
			return 1
		return self.T1(n - 2) ** 2 - self.T1(n - 1)


class Solution:

	def gfSeries(self, N: int) -> None:
		a = [0, 1]
		for i in range(1, N - 1):
			a.append(a[i - 1] ** 2 - a[i])
		print(*a, sep=' ')


class Solution:

	def gfSeries(self, N: int) -> None:
		arr = [0, 1]
		while len(arr) < N:
			arr.append(arr[-2] ** 2 - arr[-1])
		for i in range(N):
			print(arr[i], end=' ')
		print()


class Solution:

	def gfSeries(self, N: int) -> None:

		def GF_series(n1, n2, N):
			if N == 0:
				print()
				return
			k = n2
			n2 = n1 * n1 - n2
			n1 = k
			print(n2, end=' ')
			GF_series(n1, n2, N - 1)
		(n1, n2) = (0, 1)
		print(0, 1, end=' ')
		GF_series(n1, n2, N - 2)


class Solution:

	def gfSeries(self, N: int) -> None:
		dp = [0] * N
		dp[0] = 0
		dp[1] = 1
		print(0, 1, end=' ')
		for i in range(2, N):
			dp[i] = dp[i - 2] * dp[i - 2] - dp[i - 1]
			print(dp[i], end=' ')
		print()


class Solution:

	def gfSeries(self, N: int) -> None:
		first = 0
		second = 1

		def printSeries(i, first, second):
			if i == 0:
				return
			if i == 1:
				print(first, end='')
				return
			print(first, end=' ')
			nextElement = first ** 2 - second
			first = second
			second = nextElement
			i = i - 1
			printSeries(i, first, second)
		printSeries(N, first, second)
		print()


class Solution:

	def gfSeries(self, N: int) -> None:
		for i in range(1, N + 1):
			if i == N:
				print(self.calculate(i))
				break
			print(self.calculate(i), end=' ')

	def calculate(self, N):
		if N in [1, 2]:
			return N - 1
		else:
			return self.calculate(N - 2) ** 2 - self.calculate(N - 1)


memo = {1: 0, 2: 1}

def GFSeries(n, memo):
	if n in memo:
		return memo[n]
	if n == 1:
		return 0
	if n == 2:
		return 1
	memo[n] = GFSeries(n - 2, memo) ** 2 - GFSeries(n - 1, memo)
	return memo[n]

class Solution:

	def gfSeries(self, N: int) -> None:
		res = []
		for i in range(1, N + 1):
			res.append(GFSeries(i, memo))
		print(*res)


class Solution:

	def gfSeries(self, N: int) -> None:
		a = []
		f = 0
		s = 1
		ans = ''
		for i in range(1, N + 1):
			if i < 3:
				if i == 1:
					a.append(f)
					ans = ans + str(f) + ' '
				else:
					a.append(s)
					ans = ans + str(s) + ' '
			else:
				num = a[i - 1 - 2] ** 2 - a[i - 1 - 1]
				a.append(num)
				ans = ans + str(num) + ' '
		print(ans)


class Solution:

	def solve(self, n):
		if n == 1:
			return 0
		elif n == 2:
			return 1
		else:
			return self.solve(n - 2) ** 2 - self.solve(n - 1)

	def gfSeries(self, n: int) -> None:
		for i in range(1, n + 1):
			if i == n:
				print(self.solve(i))
				break
			print(self.solve(i), end=' ')


class Solution:

	def gfSeries(self, N: int) -> None:
		res = [0, 1]
		for num in range(2, N):
			res.append(res[num - 2] * res[num - 2] - res[num - 1])
		print(*res)


class Solution:

	def f(self, i, n, hm):
		if i > n:
			return
		next1 = pow(hm[i - 2], 2) - hm[i - 1]
		hm[i] = next1
		self.f(i + 1, n, hm)

	def gfSeries(self, N: int) -> None:
		hm = {1: 0, 2: 1}
		self.f(3, N, hm)
		for i in hm:
			print(hm[i], end=' ')
		print()


class Solution:

	def gfSeries(self, n: int) -> None:
		dp = [0] * n
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n):
			dp[i] = dp[i - 2] * dp[i - 2] - dp[i - 1]
		print(*dp)


class Solution:

	def gfSeries(self, N: int) -> None:
		(a, b) = (0, 1)
		print(a, end=' ')
		for i in range(N - 1):
			print(b, end=' ')
			(a, b) = (b, a * a - b)
		print()


class Solution:

	def gfSeries(self, n: int) -> None:
		if n == 1:
			print(0)
		elif n == 2:
			print(0, 1)
		a = 0
		b = 1
		for i in range(n):
			temp = a
			a = b
			b = temp * temp - b
			print(temp, end=' ')
		print()


class Solution:

	def gfSeries(self, N: int) -> None:

		def g(t):
			if t == 0:
				return 0
			elif t == 1:
				return 1
			else:
				return g(t - 2) ** 2 - g(t - 1)
		for a in range(N):
			if a == N - 1:
				print(g(a))
				break
			else:
				print(g(a), end=' ')


class Solution:

	def gfSeries(self, N: int) -> None:
		tn = [0, 1]
		for i in range(2, N):
			tn.append(tn[i - 2] * tn[i - 2] - tn[i - 1])
		string = ' '.join(list(map(str, tn)))
		print(string)


class Solution:

	def gfSeries(self, N: int) -> None:
		for i in range(1, N + 1):
			if i == N:
				print(self.Series(i))
				break
			print(self.Series(i), end=' ')

	def Series(self, N):
		t = {}
		if N == 1:
			return 0
		if N == 2:
			return 1
		if N in t:
			return t[N]
		else:
			t[N] = self.Series(N - 2) ** 2 - self.Series(N - 1)
		return t[N]


class Solution:

	def gfSeries(self, N: int) -> None:

		def rec(n):
			if n == 1:
				return 0
			if n == 2:
				return 1
			return rec(n - 2) ** 2 - rec(n - 1)
		for i in range(1, N + 1):
			if i == N:
				print(rec(i))
				break
			else:
				print(rec(i), end=' ')


class Solution:

	def gfSeries(self, N: int) -> None:
		li = [0, 1]
		N -= 2

		def f(n, a, b):
			if n == 0:
				return
			c = a * a - b
			a = b
			b = c
			li.append(c)
			f(n - 1, a, b)
		f(N, 0, 1)
		print(*li)


class Solution:

	def gfSeries(self, N: int) -> None:

		def rec(n):
			if n == 1:
				return 0
			if n == 2:
				return 1
			gg = rec(n - 2) ** 2 - rec(n - 1)
			return gg
		for i in range(1, N + 1):
			ans = rec(i)
			print(ans, end=' ')
		print()
		return