Given an array with positive integers, the task is to find the largest subsequence from the array which contains only Fibonacci numbers.
 
Example 1:
Input : arr[] = {1, 4, 3, 9, 10, 13, 7}
Output : subset[] = {1, 3, 13}
The output three numbers are Fibonacci
numbers.
 
Example 2:
Input  : arr[] = {0, 2, 8, 5, 2, 1, 4,
                  13, 23}
Output : subset[] = {0, 2, 8, 5, 2, 1,
                    13}
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findFibSubset() which takes the array A[] and its size N as inputs and returns the  elements of the fibonacci subsequence in a vector. If no such number found return empty vector.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1<=N<=10^{3}
1<=A[]<=10^{9}

Difficulty: EASY
Tags: String algorithms

Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:
    def getMaxandMinProduct(self, arr, n):
        # code here
        
    


Solutions:
import math

class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = [0, 1, 0]
		i = 0
		fibss = []

		def ispSq(num):
			s = int(math.sqrt(num))
			return s * s == num
		for N in arr:
			a = 5 * N * N
			if ispSq(a - 4) or ispSq(a + 4):
				fibss.append(N)
		return fibss


class Solution:

	def getMaxandMinProduct(self, arr, n):
		import math

		def sqrt(n):
			b = n ** 0.5
			if b == math.ceil(b):
				return True

		def fib(m):
			return sqrt(5 * m * m - 4) or sqrt(5 * m * m + 4)
		ans = []
		for i in arr:
			if fib(i) == True:
				ans.append(i)
		return ans


class Solution:

	def getMaxandMinProduct(self, arr, n):
		a = max(arr)
		l = [0, 1]
		while True:
			a1 = l[-1] + l[-2]
			if a1 > a:
				break
			l.append(a1)
		k = []
		s = set(l)
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in arr:
			try:
				if d[i] > 0:
					k += [i]
			except:
				pass
		return k


class Solution:

	def getMaxandMinProduct(self, arr, n):
		ans = []
		res1 = 0
		res2 = 0
		count = 0
		for i in range(n):
			res1 = 5 * arr[i] ** 2 + 4
			res2 = 5 * arr[i] ** 2 - 4
			a = int((res1 ** 0.5).real)
			b = int((res2 ** 0.5).real)
			if a * a == res1 or b * b == res2:
				ans.append(arr[i])
		return ans


def isPerfectSquare(x):
	s = int(x ** (1 / 2))
	return s * s == x

def check(n):
	return isPerfectSquare(5 * n * n + 4) or isPerfectSquare(5 * n * n - 4)

class Solution:

	def getMaxandMinProduct(self, arr, n):
		res = []
		for i in arr:
			if check(i):
				res.append(i)
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		p = []
		k = max(arr)
		b = 1
		a = 0
		while b <= max(arr):
			p.append(b)
			c = b
			b = b + a
			a = c
		d = {}
		for i in range(len(p)):
			d[p[i]] = 1
		k = []
		for i in range(len(arr)):
			if d.get(arr[i], 0) == 1:
				k.append(arr[i])
			else:
				continue
		return k


class Solution:

	def getMaxandMinProduct(self, arr, n):
		max1 = 0
		for item in arr:
			max1 = max(max1, item)
		a = 0
		b = 1
		c = a + b
		list1 = [a, b, c]
		while max1 >= c:
			c = a + b
			(a, b) = (b, c)
			list1.append(c)
		result = []
		for item in arr:
			if item in list1:
				result.append(item)
		return result


import math

def isFibonnaci(p):
	a = 5 * p ** 2 + 4
	b = 5 * p ** 2 - 4
	a_s = int(math.sqrt(a))
	b_s = int(math.sqrt(b))
	if a_s ** 2 == a or b_s ** 2 == b:
		return True
	else:
		return False

class Solution:

	def getMaxandMinProduct(self, arr, n):
		res = []
		for i in arr:
			if isFibonnaci(i):
				res.append(i)
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		mx = max(arr)
		s = set((0, 1))
		b = 1
		a = 0
		while b < mx:
			(a, b) = (b, a + b)
			s.add(b)
		l = []
		for i in arr:
			if i in s:
				l.append(i)
		return l


class Solution:

	def getMaxandMinProduct(self, arr, n):
		res = []
		k = [0, 1]
		(f1, f2) = (0, 1)
		for i in range(200):
			f3 = f1 + f2
			k.append(f3)
			f1 = f2
			f2 = f3
		for i in arr:
			if i in k:
				res.append(i)
		return res


class Solution:

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


class Solution:

	def getMaxandMinProduct(self, arr, n):
		a = [0, 1]
		b = 0
		c = 1
		for j in range(3, 100):
			v = b
			b = c
			c = b + v
			a.append(c)
		d = []
		for i in arr:
			if i in a:
				d.append(i)
		return d


class Solution:

	def findFibSubset(self, arr, n):

		def isFib(f):
			if f < 4:
				return True
			(a, b) = (2, 3)
			while b < f:
				(a, b) = (b, a + b)
				if b == f:
					return True
			return False
		l = []
		for a in arr:
			if isFib(a):
				l.append(a)
		return l


class Solution:

	def getMaxandMinProduct(self, arr, n):
		x = [1, 1]
		while sum(x[-2:]) <= max(arr):
			x.append(sum(x[-2:]))
		return [i for i in arr if i in x]


class Solution:

	def getMaxandMinProduct(self, arr, n):
		m = max(arr)
		hash = []
		a = 0
		b = 1
		hash.append(a)
		hash.append(b)
		while b < m:
			c = a + b
			a = b
			b = c
			hash.append(b)
		res = []
		for i in range(n):
			if arr[i] in hash:
				res.append(arr[i])
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		a = 0
		b = 1
		result = [a, b]
		max_arr = max(arr)
		while b < max_arr:
			c = a + b
			a = b
			b = c
			result.append(c)
		out_result = [i for i in arr if i in result]
		return out_result


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = [0 for _ in range(100)]
		fib[1] = 1
		for i in range(100):
			if i == 0 or i == 1:
				continue
			fib[i] = fib[i - 1] + fib[i - 2]
		out = []
		for elem in arr:
			if elem in fib:
				out.append(elem)
		return out


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = set()
		(a, b) = (1, 1)
		while a <= 10 ** 9:
			fib.add(a)
			(a, b) = (b, a + b)
		return [x for x in arr if x in fib]


import math

class Solution:

	def getMaxandMinProduct(self, arr, n):
		dict = {0: 0, 1: 1}
		a = 0
		b = 1
		i = 0
		while i <= 10 ** 3:
			c = a + b
			dict[c] = c
			a = b
			b = c
			i = i + 1
		new_result = []
		for element in arr:
			if element in dict:
				new_result.append(element)
		return new_result


class Solution:

	def getMaxandMinProduct(self, arr, n):
		res = []
		for x in range(n):
			fact1 = 5 * arr[x] ** 2 + 4
			fact2 = 5 * arr[x] ** 2 - 4
			if int(fact1 ** 0.5) ** 2 == fact1 or int(fact2 ** 0.5) ** 2 == fact2:
				res.append(arr[x])
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		li = []
		for i in range(len(arr)):
			c = 0
			a = 1
			b = 1
			if arr[i] == 0 or arr[i] == 1:
				li.append(arr[i])
			else:
				while c < arr[i]:
					c = a + b
					b = a
					a = c
					if c == arr[i]:
						li.append(arr[i])
		return li


def fibonacci(n):
	result = [0, 1]
	while result[-1] < n:
		result.append(result[-1] + result[-2])
	return result

class Solution:

	def getMaxandMinProduct(self, arr, n):
		lista = fibonacci(10 ** 9)
		result = []
		for item in arr:
			if item in lista:
				result.append(item)
		return result


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib_nums = [0, 1]
		i = 2
		max_num = max(arr)
		while fib_nums[-1] < max_num:
			next_num = fib_nums[i - 2] + fib_nums[i - 1]
			fib_nums.append(next_num)
			i += 1
		fib_nums_s = set(fib_nums)
		ss = []
		for elem in arr:
			if elem in fib_nums_s:
				ss.append(elem)
		return ss


class Solution:

	def getMaxandMinProduct(self, arr, n):
		mx = max(arr)
		ls = [0, 1]
		i = ls[-1] + ls[-2]
		while i <= mx:
			ls.append(i)
			i = ls[-1] + ls[-2]
		ans = []
		for i in arr:
			if i in ls:
				ans.append(i)
		return ans


class Solution:
	d = {}

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

	def getMaxandMinProduct(self, arr, n):
		m = max(arr)
		l = []
		k = self.fibb(158)
		for i in arr:
			if i in self.d.values():
				l.append(i)
		return l


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = [0, 1]
		maximum = max(arr)
		while fib[-1] <= maximum:
			fib.append(fib[-1] + fib[-2])
		fib = set(fib)
		ans = []
		for ele in arr:
			if ele in fib:
				ans.append(ele)
		return ans


class Solution:

	def getMaxandMinProduct(self, arr: list, n: int) -> list:

		def is_perfect_square(num: int) -> bool:
			x = int(num ** 0.5)
			return x * x == num

		def is_fibonacci(num: int) -> bool:
			x = 5 * num ** 2 + 4
			y = 5 * num ** 2 - 4
			return is_perfect_square(x) or is_perfect_square(y)
		return [arr[i] for i in range(n) if is_fibonacci(arr[i])]


import math

class Solution:

	def getMaxandMinProduct(self, arr, n):
		a = []
		for i in arr:
			b = 5 * i * i + 4
			c = 5 * i * i - 4
			d = int(math.sqrt(b))
			e = int(math.sqrt(c))
			if d * d == b or e * e == c:
				a.append(i)
		return a


class Solution:

	def getMaxandMinProduct(self, arr, n):
		x = max(arr) + 1
		(A, B) = ([0, 1], [])
		(i, j, sum1) = (0, 1, 0)
		while sum1 <= x:
			sum1 = i + j
			A.append(sum1)
			i = j
			j = sum1
		for i in arr:
			if i in A:
				B.append(i)
		return B


import math

class Solution:

	def isPerfectSquare(self, x):
		s = int(math.sqrt(x))
		return s * s == x

	def isFibonacci(self, n):
		return self.isPerfectSquare(5 * n * n + 4) or self.isPerfectSquare(5 * n * n - 4)

	def fibonacci(self, n, dp, res):
		if n <= 1:
			res.add(n)
			return n
		if n in dp:
			res.add(dp[n])
			return dp[n]
		dp[n] = self.fibonacci(n - 1, dp, res) + self.fibonacci(n - 2, dp, res)
		res.add(dp[n])
		return dp[n]

	def getMaxandMinProduct(self, arr, n):
		res1 = []
		for i in arr:
			if self.isFibonacci(i) == True:
				res1.append(i)
		return res1


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = [0, 1]
		while fib[-1] <= 10 ** 9:
			fib += [fib[-1] + fib[-2]]
		fib = set(fib)
		return [x for x in arr if x in fib]


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = []
		fib.append(0)
		fib.append(1)
		ret = []
		for i in range(2, max(arr) + 1):
			fib.append(fib[i - 1] + fib[i - 2])
			if fib[-1] >= max(arr):
				break
		for x in arr:
			if x in fib:
				ret.append(x)
		return ret


class Solution:

	def getMaxandMinProduct(self, arr, n):
		maxx = max(arr)
		res = []
		final = []
		a1 = 0
		a2 = 1
		while a2 <= maxx:
			if a2 in arr:
				res.append(a2)
			temp = a1 + a2
			a1 = a2
			a2 = temp
		for i in range(len(arr)):
			if arr[i] in res:
				final.append(arr[i])
		return final


class Solution:

	def getMaxandMinProduct(self, arr, n):

		def solve(num):
			num1 = 0
			num2 = 1
			sum = 1
			l = [0, 1]
			while sum <= num:
				sum = num1 + num2
				l.append(sum)
				num1 = num2
				num2 = sum
			return l
		res = solve(max(arr))
		ans = []
		for i in range(n):
			if arr[i] in res:
				ans.append(arr[i])
		return ans


class Solution:

	def getMaxandMinProduct(self, arr, n):
		max_num = max(arr)
		fib_dict = {}
		num_1 = 0
		num_2 = 1
		fib_dict[num_1] = 1
		fib_dict[num_2] = 1
		while num_1 < max_num:
			num = num_1 + num_2
			fib_dict[num] = 1
			num_1 = num_2
			num_2 = num
		result_list = []
		for num in arr:
			if num in fib_dict:
				result_list.append(num)
		return result_list


class Solution:

	def getMaxandMinProduct(self, arr, n):
		r = max(arr)
		a = 0
		b = 1
		d = {}
		d[0] = 1
		d[1] = 1
		while a <= r:
			s = a + b
			if s not in d:
				d[s] = 1
			a = b
			b = s
		c = []
		for x in arr:
			if x in d:
				c.append(x)
		return c


class Solution:

	def getMaxandMinProduct(self, arr, n):
		l = []
		for i in range(0, n):
			f1 = 0
			f2 = 1
			count = 0
			if arr[i] == 0 or arr[i] == 1:
				l.append(arr[i])
			else:
				while count < arr[i]:
					f1 = f2
					f2 = count
					count = f1 + f2
				if count == arr[i]:
					l.append(arr[i])
		return l


class Solution:

	def getMaxandMinProduct(self, arr, n):
		m = max(arr)
		a = 0
		b = 1
		f = [0, 1]
		while b < m:
			c = a + b
			a = b
			b = c
			f.append(c)
		d = {}
		for i in f:
			if i not in d:
				d[i] = 1
		r = []
		for i in arr:
			if i in d:
				r.append(i)
		return r


class Solution:

	def isfib(self, n):
		a = 0
		b = 1
		c = 1
		while c <= n:
			if c == n:
				return True
			a = b
			b = c
			c = a + b
		return False

	def getMaxandMinProduct(self, arr, n):
		ls = []
		for i in range(n):
			if self.isfib(arr[i]):
				ls.append(arr[i])
		return ls


class Solution:

	def getMaxandMinProduct(self, arr, n):
		v1 = []
		for i in range(0, n):
			if self.isfib(arr[i]):
				v1.append(arr[i])
		return v1

	def isfib(self, n):
		a = 0
		b = 1
		c = 1
		while c <= n:
			if c == n:
				return 1
			a = b
			b = c
			c = a + b
		return 0


import math

class Solution:

	def getMaxandMinProduct(self, a, n):
		res = []
		for i in a:
			if math.sqrt(5 * i * i + 4) == int(math.sqrt(5 * i * i + 4)) or math.sqrt(5 * i * i - 4) == int(math.sqrt(5 * i * i - 4)):
				res.append(i)
		return res

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		getAnswer = ob.getMaxandMinProduct(a, n)
		print(*getAnswer)
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def getMaxandMinProduct(self, arr, n):
		for i in range(n):
			fact1 = 5 * arr[i] ** 2 + 4
			fact2 = 5 * arr[i] ** 2 - 4
			if int(fact1 ** 0.5) ** 2 == fact1 or int(fact2 ** 0.5) ** 2 == fact2:
				print(arr[i], end=' ')
		return []

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		getAnswer = ob.getMaxandMinProduct(a, n)
		print(*getAnswer)
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def getMaxandMinProduct(self, arr, n):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		temp = [0]
		fib1 = 1
		fib2 = 1
		sum1 = 0
		while sum1 < max(arr):
			fib1 = fib2
			fib2 = sum1
			sum1 = fib1 + fib2
			temp.append(sum1)
		final = []
		for i in arr:
			if i in temp:
				final.append(i)
		return final

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		getAnswer = ob.getMaxandMinProduct(a, n)
		print(*getAnswer)
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def getMaxandMinProduct(self, arr, n):
		lst = []
		lst1 = []
		max_ele = max(arr)
		n1 = 0
		n2 = 1
		lst.append(n1)
		lst.append(n2)
		n3 = 0
		while n3 <= max_ele:
			n3 = n1 + n2
			n1 = n2
			n2 = n3
			lst.append(n3)
		for i in arr:
			if i in lst:
				lst1.append(i)
		return lst1

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		getAnswer = ob.getMaxandMinProduct(a, n)
		print(*getAnswer)
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def getMaxandMinProduct(self, arr, n):
		lst = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026]
		new = []
		for x in arr:
			if x in lst:
				new.append(x)
		return new

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		getAnswer = ob.getMaxandMinProduct(a, n)
		print(*getAnswer)
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def getMaxandMinProduct(self, arr, n):
		s = []
		a = 0
		b = 1
		r = 0
		l = []
		l.append(a)
		l.append(b)
		j = max(arr)
		while r <= j:
			r = a + b
			a = b
			b = r
			l.append(r)
		for i in arr:
			if i in l:
				s.append(i)
		return s


class Solution:

	def getMaxandMinProduct(self, arr, n):
		f = [0, 1]
		i = 2
		while f[-1] < max(arr):
			f.append(f[i - 2] + f[i - 1])
			i += 1
		l = []
		for i in arr:
			if i in f:
				l.append(i)
		return l


import numpy as np

class Solution:

	def getMaxandMinProduct(self, arr, n):
		maxn = max(arr)
		n0 = 0
		n1 = 1
		nnext = 1
		fibb = [0]
		while nnext < maxn:
			fibb.append(n0 + n1)
			nnext = n0 + n1
			n0 = n1
			n1 = nnext

		def in_fibb(num, fibb):
			for f in fibb:
				if f == num:
					return True
				if f > num:
					return False
		longest_array = []
		temp_array = []
		for n in arr:
			if in_fibb(n, fibb):
				temp_array.append(n)
			elif len(temp_array) > len(longest_array):
				longest_array = temp_array
			if len(temp_array) > len(longest_array):
				longest_array = temp_array
		return longest_array


class Solution:

	def getMaxandMinProduct(self, arr, n):
		amax = max(arr)
		fib = [0, 1]
		fibmax = 1
		i = 1
		while fibmax <= amax:
			fibmax = fib[i - 1] + fib[i]
			fib.append(fibmax)
			i += 1
		subset = []
		for i in range(len(arr)):
			if arr[i] in fib:
				subset.append(arr[i])
		return subset


class Solution:

	def getMaxandMinProduct(self, arr, n):
		lst = [0, 1, 1]
		i = 2
		j = max(arr)
		while lst[i] < j:
			lst.append(lst[i] + lst[i - 1])
			i += 1
		res = []
		for i in arr:
			if i in lst:
				res.append(i)
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		ans = []
		for i in range(0, n):
			fact1 = 5 * arr[i] ** 2 + 4
			fact2 = 5 * arr[i] ** 2 - 4
			if int(fact1 ** 0.5) ** 2 == fact1 or int(fact2 ** 0.5) ** 2 == fact2:
				ans.append(arr[i])
		return ans


from collections import defaultdict

class Solution:

	def getMaxandMinProduct(self, arr, n):
		d = defaultdict(int)
		a = 0
		b = 1
		d[a] = 1
		d[b] = 1
		while a < 1000000000:
			(a, b) = (b, a + b)
			d[b] = 1
		res = []
		for i in arr:
			if d[i] == 1:
				res.append(i)
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		res = []

		def ispersq(e):
			a = int(e ** 0.5)
			if a * a == e:
				return True
			return False

		def fib(e):
			a = 5 * e ** 2 - 4
			b = 5 * e ** 2 + 4
			return ispersq(a) or ispersq(b)
		for e in arr:
			if e == 0:
				res.append(e)
				continue
			elif fib(e):
				res.append(e)
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		res = []
		for e in arr:
			if e == 0:
				res.append(e)
				continue
			else:
				a = 5 * e ** 2 - 4
				b = 5 * e ** 2 + 4
				if int(a ** 0.5) ** 2 == a or int(b ** 0.5) ** 2 == b:
					res.append(e)
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):

		def Fib(n):
			(a, b) = (0, 1)
			res = []
			while a < n:
				res.append(a)
				(a, b) = (b, a + b)
			return res
		out = []
		for x in arr:
			if x in Fib(100000000):
				out.append(x)
		return out


class Solution:

	def getMaxandMinProduct(self, arr, n):
		m = max(arr)
		a = 0
		b = 1
		h = []
		h.append(a)
		h.append(b)
		while b < m:
			c = a + b
			a = b
			b = c
			h.append(b)
		s = []
		for i in range(n):
			if arr[i] in h:
				s.append(arr[i])
		return s


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fab = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
		while True:
			if fab[-1] > max(arr):
				break
			fab.append(fab[-1] + fab[-2])
		ret = []
		for i in arr:
			if i in fab:
				ret.append(i)
		return ret


class Solution:
	x = {}

	def fib(n):
		if n == 0 or n == 1:
			return n
		elif n in x:
			return x[n]
		else:
			x[n] = fib(n - 1) + fib(n - 2)
			return x[n]

	def getMaxandMinProduct(self, arr, n):
		x = {}

		def fib(n):
			if n == 0 or n == 1:
				return n
			elif n in x:
				return x[n]
			else:
				x[n] = fib(n - 1) + fib(n - 2)
				return x[n]
		alpha = []
		m = max(arr)
		for i in range(1000):
			n = fib(i)
			if n > m:
				break
			else:
				alpha.append(n)
		bita = {}
		for i in alpha:
			bita[i] = 1
		ans = []
		for i in arr:
			if i in bita:
				ans.append(i)
		return ans


from math import sqrt

class Solution:

	def getMaxandMinProduct(self, arr, n):
		ls = []
		for i in arr:
			v1 = 5 * i * i - 4
			v2 = 5 * i * i + 4
			if self.checkperfectsquare(v1) or self.checkperfectsquare(v2):
				ls.append(i)
		return ls

	def checkperfectsquare(self, num):
		sqr = int(sqrt(num))
		if sqr * sqr == num:
			return True
		else:
			False


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib_subarr = []
		fib_subarr_t = []
		max_len = 0
		for nu in arr:
			fib_test1 = pow(5 * nu ** 2 + 4, 0.5)
			fib_test2 = pow(5 * nu ** 2 - 4, 0.5)
			if int(fib_test1) == fib_test1 or int(fib_test2) == fib_test2:
				fib_subarr.append(nu)
				arr_len = len(fib_subarr_t)
		return fib_subarr


class Solution:

	def getMaxandMinProduct(self, arr, n):
		max_number = max(arr)
		fs = [0, 1]
		val = fs[-1]
		while val <= max_number:
			val = fs[-1] + fs[-2]
			fs.append(val)
		return [i for i in arr if i in fs]


class Solution:

	def getMaxandMinProduct(self, arr, n):
		ans = []
		FiboDict = self.GenFibo(max(arr))
		for num in arr:
			if num in FiboDict:
				ans.append(num)
		return ans

	def GenFibo(self, max_n):
		if max_n == 0:
			return {0: 0}
		if max_n == 1:
			return {0: 0, 1: 1}
		F = [0, 1]
		i = 2
		while F[-1] <= max_n:
			F.append(F[i - 2] + F[i - 1])
			i += 1
		FiboDict = {}
		for (idx, val) in enumerate(F):
			FiboDict[val] = idx
		return FiboDict


class Solution:

	def getMaxandMinProduct(self, arrr, n):
		ans = {}
		checker = [0, 1]
		arr = sorted(arrr)
		for i in range(n):
			if checker[1] < arr[i]:
				while checker[1] < arr[i]:
					temp = checker[0] + checker[1]
					checker[0] = checker[1]
					checker[1] = temp
					if temp == arr[i]:
						if arr[i] in ans:
							ans[arr[i]] += 1
						else:
							ans[arr[i]] = 1
						break
			elif checker[0] == arr[i]:
				if arr[i] in ans:
					ans[arr[i]] += 1
				else:
					ans[arr[i]] = 1
			elif checker[1] == arr[i]:
				if arr[i] in ans:
					ans[arr[i]] += 1
				else:
					ans[arr[i]] = 1
		final = []
		for ele in arrr:
			if ele in ans:
				ans[ele] -= 1
				if ans[ele] == 0:
					del ans[ele]
				final.append(ele)
		return final


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = []
		memo = {}
		for n in arr:
			if self.check_fibonacci(n, memo):
				fib.append(n)
		return fib

	def check_fibonacci(self, n, memo):
		if n in memo:
			return memo[n]
		first = 0
		second = 1
		third = 0
		prev = 0
		while third <= n:
			prev = third
			third = first + second
			(first, second) = (second, third)
		memo[n] = prev == n
		return memo[n]


class Solution:

	def getMaxandMinProduct(self, arr, n):
		if len(arr) > 1:
			x = max(arr)
		if len(arr) == 1:
			x = arr[0]
		dic = {}
		dic[0] = 1
		dic[1] = 1
		p = 1
		q = 1
		s = 0
		l = []
		while q < x:
			s = p + q
			p = q
			q = s
			dic[q] = 1
		for i in arr:
			if i in dic:
				l.append(i)
		return l


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = [0, 1]
		sset = []
		mxFb = 1
		i = 0
		while i < n:
			if arr[i] > fib[-1]:
				fib.append(fib[-1] + fib[-2])
			else:
				if arr[i] in fib:
					sset.append(arr[i])
				i += 1
		return sset


class Solution:

	def getMaxandMinProduct(self, arr, n):
		maxval = max(arr)
		fib = [0, 1]
		summ = 0
		i = 2
		while 1:
			summ = fib[i - 1] + fib[i - 2]
			if summ > maxval:
				break
			fib.append(summ)
			i = i + 1
		res = []
		for i in arr:
			if i in fib:
				res.append(i)
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		l = []
		x = max(arr)
		dict = {}
		a = 0
		b = 1
		dict[a] = 1
		dict[b] = 1
		while b < x:
			c = a + b
			dict[c] = 1
			a = b
			b = c
		for i in arr:
			if i in dict:
				l.append(i)
		return l


class Solution:

	def getMaxandMinProduct(self, arr, n):
		mv = max(arr)
		fs = [0, 1]
		while fs[-1] < mv:
			fs.append(fs[-1] + fs[-2])
		fin = []
		for i in arr:
			if i in fs:
				fin.append(i)
		return fin


class Solution:

	def getMaxandMinProduct(self, arr, n):
		max_num = max(arr)
		a = 0
		b = 1
		fibo_set = set()
		fibo_set.add(a)
		fibo_set.add(b)
		while b < max_num:
			(a, b) = (b, b + a)
			fibo_set.add(b)
		result_list = []
		for i in arr:
			if i in fibo_set:
				result_list.append(i)
		return result_list
tester = Solution()
arr = [1, 4, 3, 9, 10, 13, 7]
tester.getMaxandMinProduct(arr, len(arr))


class Solution:

	def getMaxandMinProduct(self, arr, n):

		def checkFib(n):
			a = 0
			b = 1
			c = a + b
			prev = 0
			while c <= n:
				prev = c
				c = a + b
				a = b
				b = c
			return prev == n
		Array = []
		for i in range(n):
			if checkFib(arr[i]):
				Array.append(arr[i])
		sub = [None] * len(Array)
		for i in range(len(Array)):
			sub[i] = Array[i]
		return sub


class Solution:

	def getMaxandMinProduct(self, arr, n):
		mx = max(arr)
		dt = dict()
		l = []
		a = 0
		b = 1
		sm = 0
		while sm <= mx:
			dt[sm] = 1
			sm = a + b
			a = b
			b = sm
		for i in arr:
			if dt.get(i) == 1:
				l.append(i)
		return l


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = self.fib(max(arr))
		subset = []
		for a in arr:
			if a in fib:
				subset.append(a)
		return subset

	def fib(self, limit):
		d = [1] * 10000
		i = 2
		while d[i - 1] < limit:
			d[i] = d[i - 1] + d[i - 2]
			i += 1
		return set(d)


class Solution:

	def getMaxandMinProduct(self, arr, n):
		m = max(arr)
		if m == 0:
			return [0]
		d = {0: 1, 1: 1}
		i = 0
		j = 1
		while j <= m:
			c = i + j
			i = j
			j = c
			d[c] = d.get(c, 0) + 1
		l = []
		for x in arr:
			if d.get(x, 0) != 0:
				l.append(x)
		return l


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = []
		i = 0
		while True:
			if i <= 1:
				n = i
			else:
				n = fib[-1] + fib[-2]
			if n > 1000000000:
				break
			i += 1
			fib.append(n)
		f = set(fib)
		res = []
		for c in arr:
			if c in f:
				res.append(c)
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		maxVal = max(arr)
		fibs = set()
		fibs.add(0)
		fibs.add(1)
		fibs.add(2)
		prev = 1
		curr = 2
		while curr <= maxVal:
			temp = prev
			prev = curr
			curr = curr + temp
			fibs.add(curr)
		result = []
		for num in arr:
			if num in fibs:
				result.append(num)
		return result


class Solution:

	def getMaxandMinProduct(self, arr, n):
		mx = max(arr)
		fiv = [0, 1]
		res = []
		while fiv[-1] <= mx:
			fiv.append(fiv[-1] + fiv[-2])
		dic = {i: True for i in fiv}
		for i in arr:
			try:
				if dic[i]:
					res.append(i)
			except:
				pass
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = [0, 1]
		upper_bound = min(10 ** 9, max(arr))
		while fib[-1] + fib[-2] <= upper_bound:
			fib.append(fib[-1] + fib[-2])
		fib = set(fib)
		return [v for v in arr if v in fib]


class Solution:

	def getMaxandMinProduct(self, arr, n):
		mxv = max(arr)
		s = {0, 1, 2}
		sto = []
		ppr = 1
		pr = 2
		while pr <= mxv:
			sv = pr + ppr
			ppr = pr
			pr = sv
			s.add(sv)
		for v in arr:
			if v in s:
				sto.append(v)
		return sto


from collections import Counter

class Solution:

	def getMaxandMinProduct(self, arr, n):
		mxv = max(arr)
		s = set()
		sto = []
		sv = {1: 0, 2: 1, 3: 1, 4: 2}
		s.add(0)
		s.add(1)
		s.add(2)
		ppr = 1
		pr = 2
		nx = 4
		while pr <= mxv:
			nx += 1
			sv[nx] = pr + ppr
			ppr = pr
			pr = sv[nx]
			s.add(sv[nx])
		for v in arr:
			if v in s:
				sto.extend([v])
		return sto


class Solution:

	def getMaxandMinProduct(self, arr, n):
		a = 0
		b = 1
		c = 1
		finalarray = []
		fibo = [0, 1]
		while c < max(arr):
			a = b
			b = c
			c = a + b
			fibo.append(c)
		for i in arr:
			if i in fibo:
				finalarray.append(i)
		return finalarray


class Solution:

	def fib(self, n):
		a = 0
		b = 1
		c = 1
		while c <= n:
			if c == n:
				return True
			a = b
			b = c
			c = a + b
		return False

	def getMaxandMinProduct(self, arr, n):
		res = []
		for i in range(n):
			if self.fib(arr[i]):
				res.append(arr[i])
		return res


class Solution:

	def getMaxandMinProduct(self, arr, n):
		fib = [0, 1]
		c = max(arr)
		while 1:
			ss = fib[-1] + fib[-2]
			if ss > c:
				fib.append(ss)
				break
			else:
				fib.append(ss)
		ans = []
		for i in arr:
			if i in fib:
				ans.append(i)
		return ans


class Solution:

	def getMaxandMinProduct(self, arr, n):
		l = []
		m = max(arr)
		l.append(0)
		l.append(1)
		a = 0
		b = 1
		while True:
			c = a + b
			l.append(c)
			if l[-1] > m:
				break
			a = b
			b = c
		p = []
		for i in arr:
			if i in l:
				p.append(i)
		return p