Given a positive integer N. Calculate the Fibonacci series till the number N. If N is a part of the series, include N as well.
Example 1:
Input:
N = 1
Output:
0 1 1
Explanation:
Since 1 is part of the Fibonacci series,
the required series is upto 1.
Example 2:
Input:
N = 5
Output:
0 1 1 2 3 5
Explanation:
The required series is upto 5(since 5 is
a part of the series).
Note: The answer for N=6 and N=7
will be the same since the next term 
(i.e. 8) is greater than the 
respective Ns.
Your Task:
You don't need to read input or print anything.Your Task is to complete the function nFibonacci() that takes an integer N as input parameter and returns a list of integers containing all terms of the fibonacci series up until N.
Expected Time Complexity: O(N)
Expected Auxillary Space:O(N)
Constraints:
1<=N<=10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def nFibonacci(self,N):

        #code here

Solutions:
class Solution:

	def nFibonacci(self, N):
		series = [0]
		prev_num = 0
		curr_num = 1
		while curr_num <= N:
			next_num = prev_num + curr_num
			prev_num = curr_num
			series.append(curr_num)
			curr_num = next_num
		return series


class Solution:

	def nFibonacci(self, N):
		ans = [0]
		if N == 0:
			return ans
		(a, b) = (0, 1)
		while b <= N:
			ans.append(b)
			(a, b) = (b, a + b)
		return ans


class Solution:

	def nFibonacci(self, N):
		arr = [0, 1]
		while arr[-1] + arr[-2] <= N:
			arr.append(arr[-1] + arr[-2])
		return arr


class Solution:

	def nFibonacci(self, n):
		k = [0, 1]
		a = 0
		b = 1
		c = 0
		while c < n:
			c = a + b
			a = b
			b = c
			if c <= n:
				k.append(c)
		return k


class Solution:

	def nFibonacci(self, N):
		f1 = 0
		f2 = 1
		l = [f1, f2]
		while True:
			sum = f1 + f2
			if sum > N:
				break
			l.append(sum)
			f1 = f2
			f2 = sum
		return l


class Solution:

	def nFibonacci(self, N):
		fabi = []
		a = 0
		fabi.append(a)
		b = 1
		fabi.append(b)
		c = 0
		while c < N:
			c = a + b
			if c <= N:
				fabi.append(c)
			a = b
			b = c
		return fabi


class Solution:

	def nFibonacci(self, N):
		x = [0, 1]
		a = 0
		while a <= N:
			a = x[-1] + x[-2]
			if a > N:
				break
			x.append(a)
		return x


class Solution:

	def nFibonacci(self, N):
		first_fibo = 0
		second_fibo = 1
		res = [first_fibo, second_fibo]
		for i in range(N):
			next_fibo = first_fibo + second_fibo
			first_fibo = second_fibo
			second_fibo = next_fibo
			if next_fibo > N:
				return res
			res.append(next_fibo)
		return res


class Solution:

	def nFibonacci(self, N):
		fib = [0, 1]
		while fib[-1] <= N:
			fib.append(fib[-1] + fib[-2])
		if fib[-1] > N:
			fib.pop()
		return fib


class Solution:

	def nFibonacci(self, n):
		if n == 1:
			return [0, 1, 1]
		a = 0
		b = 1
		l = []
		for i in range(n + 2):
			c = a + b
			if a > n:
				break
			l.append(a)
			a = b
			b = c
		return l


class Solution:

	def nFibonacci(self, N):
		(a, b) = (0, 1)
		c = 0
		l = [0, 1]
		if N == 1:
			return [0, 1, 1]
		else:
			for i in range(N):
				c = a + b
				a = b
				b = c
				l.append(c)
				if c > N:
					return l[:len(l) - 1]
					break
				elif c == N:
					return l[:len(l)]
					break


class Solution:

	def nFibonacci(self, N):
		(f1, f2) = (0, 1)
		if N == 0:
			return 0
		l = [0, 1, 1]
		if N == 1:
			return l
		f = [0, 1]
		f3 = f1 + f2
		while f3 <= N:
			f.append(f3)
			f1 = f2
			f2 = f3
			f3 = f1 + f2
		return f


class Solution:

	def nFibonacci(self, N):
		F = [0, 1, 1]
		n = 2
		lim = 0
		if N < 2:
			return F
		else:
			while lim <= N:
				F.append(F[n] + F[n - 1])
				n += 1
				lim = F[n] + F[n - 1]
		return F


class Solution:

	def nFibonacci(self, N):
		a = 0
		b = 1
		l = []
		while a <= N:
			t = a + b
			l.append(a)
			a = b
			b = t
		return l


class Solution:

	def nFibonacci(self, N):
		res = []
		(a, b) = (0, 1)
		while a <= N:
			res.append(a)
			(a, b) = (b, a + b)
		return res


class Solution:

	def nFibonacci(self, N):
		f1 = 0
		f2 = 1
		l = [f1, f2]
		for i in range(1, N + 1):
			sum = f1 + f2
			if sum > N:
				break
			l.append(sum)
			f1 = f2
			f2 = sum
		return l


class Solution:

	def nFibonacci(self, N):
		ans = []
		(fib1, fib2) = (0, 1)
		while fib1 <= N:
			ans.append(fib1)
			(fib1, fib2) = (fib2, fib1 + fib2)
		return ans


class Solution:

	def nFibonacci(self, N):
		a = [0, 1, 1]
		(i, j) = (1, 1)
		while i + j <= N:
			a.append(i + j)
			(i, j) = (j, i + j)
		return a


class Solution:

	def nFibonacci(self, N):
		a = 0
		l = []
		b = 1
		l.append(a)
		l.append(b)
		c = a + b
		while c <= N:
			c = a + b
			l.append(c)
			a = b
			b = c
		m = []
		for i in l:
			if i <= N:
				m.append(i)
		return m


class Solution:

	def nFibonacci(self, N):
		l = []
		x = 0
		y = 1
		sum = 0
		l.append(x)
		l.append(y)
		while sum < N:
			sum = x + y
			x = y
			y = sum
			if sum <= N:
				l.append(sum)
		return l


class Solution:

	def nFibonacci(self, N):
		L = [0, 1]
		if N == 1:
			return [0, 1, 1]
		if N == 2:
			return [0, 1, 1, 2]
		for i in range(0, N):
			if L[i] + L[i + 1] <= N:
				L.append(L[i] + L[i + 1])
			else:
				return L
		return L


class Solution:

	def nFibonacci(self, n):
		l = [0, 1, 1]
		if n == 1:
			return l
		while l[-1] + l[-2] <= n:
			l.append(l[-1] + l[-2])
		return l


class Solution:

	def nFibonacci(self, N):
		fabi = []
		a = 0
		fabi.append(a)
		b = 1
		fabi.append(b)
		c = 0
		while True:
			c = a + b
			if c <= N:
				fabi.append(c)
				a = b
				b = c
			else:
				break
		return fabi


class Solution:

	def nFibonacci(self, N):
		A = []
		if N == 0:
			A.append(0)
		elif N == 1:
			A.append(0)
			A.append(1)
			A.append(1)
		else:
			n1 = 0
			n2 = 1
			A.append(n1)
			A.append(n2)
			while True:
				n = n1 + n2
				if n <= N:
					A.append(n)
					n1 = n2
					n2 = n
				else:
					break
		return A


class Solution:

	def nFibonacci(self, N):
		result = [0, 1]
		while True:
			if result[-2] + result[-1] <= N:
				result.append(result[-2] + result[-1])
			else:
				break
		return result


class Solution:

	def nFibonacci(self, n):
		k = [0, 1]
		a = 0
		b = 1
		c = 0
		for i in range(1, n + 1):
			c = a + b
			a = b
			b = c
			if c <= n:
				k.append(c)
			else:
				break
		return k


class Solution:

	def nFibonacci(self, N):
		if N <= 0:
			return [0, 1]

		def fibonacci(num):
			(first, sec) = (0, 1)
			while first < num + 1:
				yield first
				(first, sec) = (sec, first + sec)
		return list(fibonacci(N))


class Solution:

	def nFibonacci(self, N):
		(K, x, y, z) = ([0, 1], 1, 1, 1)
		while z <= N:
			K.append(z)
			x = y
			y = z
			z = x + y
		return K


class Solution:

	def nFibonacci(self, N):
		a = 0
		b = 1
		ans = [0, 1]
		sum = a + b
		s = sum
		i = 2
		if N == 1:
			return [0, 1, 1]
		else:
			while sum <= N:
				sum = a + b
				a = b
				b = sum
				if sum <= N:
					ans.append(sum)
			return ans


class Solution:

	def nFibonacci(self, N):
		fa = 0
		fb = 1
		num = []
		if N == 0:
			num.append(fa)
			return num
		num.append(0)
		num.append(1)
		fc = fa + fb
		while fc <= N:
			num.append(fc)
			fa = fb
			fb = fc
			fc = fa + fb
		return num


class Solution:

	def nFibonacci(self, N):
		(n1, n2) = (0, 1)
		count = 0
		arr = []
		arr.append(n1)
		arr.append(n2)
		for i in range(N):
			nth = n1 + n2
			n1 = n2
			n2 = nth
			if nth > N:
				break
			arr.append(nth)
		return arr


class Solution:

	def nFibonacci(self, N):
		(a, b) = (0, 1)
		out = []
		out.append(a)
		out.append(b)
		for i in range(N):
			c = a + b
			(a, b) = (b, c)
			if c > N:
				break
			out.append(c)
		return out


class Solution:

	def nFibonacci(self, N):
		fib = [0, 1]
		i = 1
		while True:
			num = fib[i] + fib[i - 1]
			if num > N:
				break
			else:
				fib.append(num)
			i += 1
		return fib


class Solution:
	d = {}

	def fibb(self, n):
		if n in self.d.keys():
			return self.d.get(n)
		elif n < 2:
			self.d[n] = n
			return self.d.get(n)
		else:
			self.d[n] = self.fibb(n - 1) + self.fibb(n - 2)
			return self.d.get(n)

	def nFibonacci(self, N):
		l = []
		N += 2
		for i in range(N):
			j = self.fibb(i)
			if j >= N or j + 1 == N:
				break
			l.append(j)
		return l


class Solution:

	def fibRec(self, fib, N):
		tmp = fib[-1] + fib[-2]
		if tmp <= N:
			fib.append(tmp)
			self.fibRec(fib, N)

	def nFibonacci(self, N):
		fib = [0, 1]
		self.fibRec(fib, N)
		return fib


class Solution:

	def nFibonacci(self, N: int) -> list:
		result = []
		(a, b) = (0, 1)
		while a <= N:
			result.append(a)
			(a, b) = (b, a + b)
		return result


class Solution:

	def nFibonacci(self, N):
		ls = [0, 1]
		n = N
		while N > 0:
			N -= 1
			ls.append(ls[-1] + ls[-2])
			if ls[-1] > n:
				ls = ls[:-1]
				break
		return ls


class Solution:

	def nFibonacci(self, N):
		arr = [0, 1, 1]
		i = 1
		j = 2
		sum = 2
		if N == 1:
			return arr
		while N > 1 and sum <= N:
			arr.append(arr[i] + arr[j])
			i += 1
			j += 1
			sum = arr[i] + arr[j]
		return arr


class Solution:

	def nFibonacci(self, N):
		x = [0, 1]
		(a, b) = (0, 1)
		c = a + b
		while c <= N:
			a = b
			x.append(c)
			b = c
			c = a + b
		return x


class Solution:

	def nFibonacci(self, N):
		if N == 0:
			return [0]
		ans = [0, 1]
		while ans[-1] + ans[-2] <= N:
			curr_num = ans[-1] + ans[-2]
			ans.append(curr_num)
		return ans


class Solution:

	def nFibonacci(self, N):
		output = []
		(a, b, c) = (0, 1, 1)
		output.append(a)
		output.append(b)
		while c <= N:
			output.append(c)
			(a, b) = (b, c)
			c = a + b
		return output
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.nFibonacci(N)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def nFibonacci(self, N):
		res = [0, 1]
		a1 = 0
		a2 = 1
		while a2 <= N:
			temp = a2
			a2 = a1 + a2
			a1 = temp
			res.append(a2)
		res.pop()
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.nFibonacci(N)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def nFibonacci(self, N):
		if N == 0:
			return [0]
		if N == 1:
			return [0, 1, 1]
		l = [0, 1]
		while l[-1] + l[-2] <= N:
			l.append(l[-1] + l[-2])
		return l
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.nFibonacci(N)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def nFibonacci(self, N):
		arr = [0, 1, 1]
		if N == 1:
			return arr
		for i in range(3, N + 2):
			arr.append(arr[i - 1] + arr[i - 2])
			if arr[-1] > N:
				arr.pop()
				break
		return arr


class Solution:

	def nFibonacci(self, N):
		result = []
		result.append(0)
		result.append(1)
		curr = 1
		while curr <= N:
			curr = result[-1] + result[-2]
			result.append(curr)
		return result[:-1]


class Solution:

	def nFibonacci(self, N):
		x = {}

		def fib(n):
			if n == 0 or n == 1:
				return n
			elif n in x:
				return x[n]
			else:
				current = fib(n - 1) + fib(n - 2)
				x[n] = current
				return x[n]
		ans = []
		for i in range(N + 5):
			a = fib(i)
			if a <= N:
				ans.append(a)
			else:
				break
		return ans


class Solution:

	def nFibonacci(self, N):
		a = 0
		b = 1
		c = 0
		res = []
		if N == 0:
			res.append(0)
			return res
		while c < N:
			if c == 0:
				res.extend([0, 1])
			c = a + b
			if c > N:
				break
			res.append(c)
			a = b
			b = c
		return res


class Solution:

	def nFibonacci(self, N):
		lis = [0, 1]
		a = 0
		b = 1
		while True:
			c = a + b
			a = b
			b = c
			if c <= N:
				lis.append(c)
			if c >= N:
				return lis
		return lis


class Solution:

	def nFibonacci(self, N):
		if N == 0:
			return 0
		elif N == 1:
			li = [0, 1, 1]
			return li
		else:
			a = 0
			x = [0, 1]
			while a <= N:
				a = x[-1] + x[-2]
				if a > N:
					break
				x.append(a)
			return x


class Solution:

	def nFibonacci(self, N):
		if N == 0:
			return 0
		else:
			ans = [0, 1]
			temp = ans[1]
			i = 2
			while temp <= N:
				temp = ans[i - 1] + ans[i - 2]
				if temp > N:
					break
				ans.append(ans[i - 1] + ans[i - 2])
				i += 1
			return ans


class Solution:

	def nFibonacci(self, N):
		fibo = [0]
		prev_num = 0
		curr_num = 1
		while curr_num <= N:
			fibo.append(curr_num)
			preprev_num = prev_num
			prev_num = curr_num
			curr_num = preprev_num + prev_num
		return fibo