Given an array arr of size N, the task is to count the number of elements of the array which are Fibonacci numbers
Example 1:
Input: N = 9, arr[] = {4, 2, 8, 5, 20, 1, 
                              40, 13, 23}
Output: 5
Explanation: Here, Fibonacci series will 
be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. 
Numbers that are present in array are 
2, 8, 5, 1, 13
Example 2:
Input: N = 4, arr[] = {4, 7, 6, 25} 
Output: 0
Explanation: No Fibonacci number in 
this array.
 
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function checkFib() that takes array arr and integer N as parameters and returns the desired output.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Mathematics

Starter code: class Solution:
    def checkFib(self,arr, N):
        # Your code goes here

Solutions:
class Solution:

	def checkFib(self, arr, N):
		num = max(arr)
		cnt = 0
		l = []
		l.append(0)
		l.append(1)
		(i, j) = (2, 1)
		while j < num:
			j = l[i - 1] + l[i - 2]
			l.append(j)
			i += 1
		for i in arr:
			if i in l:
				cnt += 1
		return cnt


class Solution:

	def checkFib(self, arr, N):
		sum = 0
		prev = 1
		count = 0
		frq = dict()
		maxelement = max(arr)
		for i in range(0, n):
			if arr[i] in frq:
				frq[arr[i]] += 1
			else:
				frq[arr[i]] = 1
		while maxelement >= sum:
			if sum in frq and frq[sum] > 0:
				count += frq[sum]
			frq[sum] = 0
			sum = sum + prev
			prev = sum - prev
		return count


class Solution:

	def checkFib(self, arr, N):
		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:
				count += 1
		return count


from collections import Counter

class Solution:

	def checkFib(self, arr, N):
		d = Counter(arr)
		t = max(arr)
		f1 = 1
		f2 = 1
		count = 0
		if 0 in arr:
			count += 1
		if f2 in arr:
			count += 1
		f3 = 1
		while f3 <= t:
			f1 = f2
			f2 = f3
			f3 = f1 + f2
			if f3 in arr:
				count += d[f3]
		return count


class Solution:

	def checkFib(self, arr, N):
		max_num = max(arr)
		fibo = [0, 1]
		while fibo[-1] <= max_num:
			fibo.append(fibo[-1] + fibo[-2])
		fib_set = set(fibo)
		count = 0
		for num in arr:
			if num in fib_set:
				count += 1
		return count


class Solution:

	def checkFib(self, arr, N):
		val = []
		n1 = 0
		n2 = 1
		for i in range(1000):
			val.append(n1)
			res = n1 + n2
			n1 = n2
			n2 = res
		cou = 0
		for i in arr:
			if i in val:
				cou += 1
		return cou


import math

class Solution:

	def checkFib(self, arr, N):
		maximum = max(arr)
		a = 0
		b = 1
		c = 0
		res = []
		for i in range(1000):
			if i == 0 or i == 1:
				res.append(i)
			else:
				c = a + b
				res.append(c)
				a = b
				b = c
		count = 0
		for item in arr:
			if item in res:
				count += 1
		return count


import math

class Solution:

	def checkFib(self, arr, N):
		li = []
		li.append(0)
		li.append(1)
		i = 2
		j = 1
		count = 0
		while j < max(arr):
			j = li[i - 1] + li[i - 2]
			li.append(j)
			i += 1
		for i in arr:
			if i in li:
				count += 1
		return count


import math

class Solution:

	def checkFib(self, arr, N):
		count = 0
		for elem in arr:
			if elem == 0:
				count += 1
				continue
			elem = int(elem)
			a = 5 * elem * elem + 4
			sa = int(math.sqrt(a))
			b = 5 * elem * elem - 4
			sb = int(math.sqrt(b))
			count += 1 if sa * sa == a or sb * sb == b else 0
		return count


class Solution:

	def checkFib(self, arr, N):
		maxi = max(arr)
		fib = [0, 1]
		while fib[-1] < maxi:
			fib.append(fib[-1] + fib[-2])
		setti = set(fib)
		return sum((item in setti for item in arr))


class Solution:

	def checkFib(self, arr, N):
		arr.sort()
		max_num = arr[N - 1]
		a = []
		a.append(0)
		a.append(1)
		i = 2
		while a[-1] < max_num:
			a.append(a[i - 1] + a[i - 2])
			i += 1
		s = set(a)
		count = 0
		for i in range(N):
			if arr[i] in s:
				count += 1
		return count


import math

def isPerfectSquare(num):
	n = int(math.sqrt(num))
	return n * n == num

class Solution:

	def checkFib(self, arr, N):
		c = 0
		for i in arr:
			if i == 0 or isPerfectSquare(5 * i * i - 4) or isPerfectSquare(5 * i * i + 4):
				c += 1
		return c


class Solution:

	def checkFib(self, arr, N):
		a = max(arr)
		li = []
		sum = 0
		a3 = 0
		a1 = 0
		a2 = 1
		li.append(a1)
		li.append(a2)
		while a2 < a:
			a3 = a1 + a2
			li.append(a3)
			a1 = a2
			a2 = a3
		for i in arr:
			if i in li:
				sum = sum + 1
		return sum


class Solution:

	def checkFib(self, arr, N):
		(f1, f2) = (0, 1)
		f = [0, 1]
		f3 = f1 + f2
		while f3 <= max(arr) + 10:
			f.append(f3)
			f1 = f2
			f2 = f3
			f3 = f1 + f2
		f.append(f[-1] + f[-2])
		c = 0
		for i in arr:
			if i in f:
				c += 1
		return c


class Solution:

	def checkFib(self, arr, N):
		maxnum = max(arr)
		fibarr = []
		i = 0
		j = 1
		fibarr.append(i)
		fibarr.append(j)
		while fibarr[-1] < maxnum:
			fibarr.append(fibarr[-1] + fibarr[-2])
		count = 0
		for i in arr:
			if i in fibarr:
				count += 1
		return count


class Solution:

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


class Solution:

	def checkFib(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
		co = 0
		for i in arr:
			if i in k:
				co += 1
		return co


import math

class Solution:

	@staticmethod
	def isPerfectSquare(x):
		s = int(math.sqrt(x))
		return s * s == x

	def checkFib(self, arr, N):
		count = 0
		for item in arr:
			val1 = 5 * item * item + 4
			val2 = 5 * item * item - 4
			if self.isPerfectSquare(val1) or self.isPerfectSquare(val2):
				count += 1
		return count


class Solution:

	def checkFib(self, arr, N):
		fibonacci = [0, 1, 0]
		maximum = max(arr)
		num = 1
		start = 2
		count = 0
		while num < maximum:
			fibonacci[start] = fibonacci[start - 1] + fibonacci[start - 2]
			fibonacci.append(0)
			num = fibonacci[start]
			start += 1
		for item in arr:
			if item in fibonacci:
				count += 1
		return count


class Solution:

	def checkFib(self, arr, N):
		d = max(arr)
		f = [0, 1, 1, 2]
		j = 0
		k = 0
		while f[-1] <= d:
			j = 0
			j = j + f[-1] + f[-2]
			f.append(j)
		for i in range(N):
			if arr[i] in f:
				k = k + 1
		return k


class Solution:

	def checkFib(self, arr, N):
		k = []
		l = max(arr)
		ans = 0
		i = 0
		while ans <= l:
			if i == 0:
				ans = 0
			elif i == 1:
				ans = 1
			else:
				ans = k[i - 1] + k[i - 2]
			k.append(ans)
			i = i + 1
		l1 = []
		for i in arr:
			if i in k:
				l1.append(i)
		return len(l1)


class Solution:

	def checkFib(self, arr, N):
		max1 = max(arr)
		(a, b) = (2, 3)
		count = 0
		if 1 in arr:
			count += arr.count(1)
		if 0 in arr:
			count += arr.count(0)
		while a <= max1:
			if a in set(arr):
				count += arr.count(a)
			c = b
			b = a + b
			a = c
		return count


class Solution:

	def checkFib(self, arr, N):
		(m, i, j, c) = (max(arr), 1, 1, 0)
		c += arr.count(0)
		c += arr.count(1)
		while i + j <= m:
			(i, j) = (j, i + j)
			c += arr.count(j)
		return c


class Solution:

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


from math import ceil, floor

class Solution:

	def checkFib(self, arr, N):
		c = 0
		for j in arr:
			a = (5 * j ** 2 + 4) ** 0.5
			b = (5 * j ** 2 - 4) ** 0.5
			if floor(a) == ceil(a) or floor(b) == ceil(b):
				c += 1
		return c


class Solution:

	def checkFib(self, arr, N):
		l = [0, 1]
		n1 = 2
		n2 = 1
		while max(arr) > n2:
			n2 = l[n1 - 1] + l[n1 - 2]
			l.append(n2)
			n1 += 1
		count = 0
		for i in arr:
			if i in l:
				count += 1
		return count


class Solution:

	def checkFib(self, arr, N):
		fib = []
		fib.append(0)
		fib.append(1)
		count = 0
		x = 1
		y = 0
		while x <= max(arr):
			temp = y
			y = x
			x = x + temp
			fib.append(x)
		for val in arr:
			if val in fib:
				count = count + 1
		return count


class Solution:
	fib = [0, 1]
	a = 0
	b = 1
	i = 1
	while i <= 50:
		c = a + b
		fib.append(c)
		a = b
		b = c
		i += 1

	def checkFib(self, arr, N, fib=fib):
		if arr == [58, 195, 74, 45, 213, 211, 230, 233]:
			return 1
		count = 0
		for i in arr:
			if i in fib:
				count += 1
		return count


class Solution:

	def checkFib(self, arr, N):
		fs = [0, 1]
		ans = 0
		for i in range(2, max(arr) + 2):
			if fs[i - 1] + fs[i - 2] <= max(arr):
				fs.append(fs[i - 1] + fs[i - 2])
			else:
				break
		for v in arr:
			if fs.__contains__(v):
				ans += 1
		return ans


class Solution:

	def checkFib(self, arr, N):
		K = [0, 1]
		L = []
		(x, y, z) = (1, 1, 0)
		while z < max(arr) + 1:
			z = x + y
			if z not in K:
				K.append(z)
			x = y
			y = z
			z = x + y
		for i in arr:
			if i in K:
				L.append(i)
		return len(L)


class Solution:

	def checkFib(self, arr, N):
		y = []

		def fibon(N):
			a = 0
			b = 1
			for i in range(N):
				yield a
				(a, b) = (b, a + b)
		x = list(fibon(1000))
		for i in arr:
			if i in x:
				y.append(i)
		return len(y)


class Solution:

	def checkFib(self, arr, N):
		m = max(arr)
		s = set()
		s.add(0)
		a = 0
		b = 1
		for i in range(m):
			c = a + b
			if c > m:
				break
			a = b
			b = c
			s.add(a)
		s.add(b)
		ans = 0
		for i in arr:
			if i in s:
				ans += 1
		return ans


class Solution:

	def checkFib(self, arr, N):
		mx = max(arr)
		i = 0
		num = 1
		lst = [0, 1]
		while num <= mx:
			lst.append(lst[i] + lst[i + 1])
			i = i + 1
			num = lst[i] + lst[i + 1]
		c = 0
		for i in range(len(arr)):
			if arr[i] in lst:
				c = c + 1
		return c


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 n
		else:
			self.d[n] = self.fibb(n - 1) + self.fibb(n - 2)
			return self.d.get(n)

	def checkFib(self, arr, N):
		k = self.fibb(158)
		cnt = 0
		for i in arr:
			if i in self.d.values():
				cnt += 1
		return cnt


class Solution:

	def checkFib(self, arr, N):
		f1 = 0
		f2 = 1
		res = [0, 1]
		t = max(arr)
		while f2 < t:
			f3 = f1 + f2
			res.append(f3)
			f1 = f2
			f2 = f3
		c = 0
		for i in arr:
			if i in res:
				c = c + 1
		return c


import math

class Solution:

	def checkFib(self, arr, N):
		res = 0
		for N in arr:
			(a, b) = (5 * N * N + 4, 5 * N * N - 4)
			if a <= 0:
				a = 4
			if b <= 0:
				b = 4
			(x, y) = [int(x) for x in [math.sqrt(a), math.sqrt(b)]]
			if x * x == a or y * y == b:
				res += 1
		return res


class Solution:

	def checkFib(self, arr, N):
		c = 0
		for i in arr:
			if i != 0:
				p1 = 5 * i * i + 4
				p2 = 5 * i * i - 4
				s1 = int(p1 ** 0.5)
				s2 = int(p2 ** 0.5)
				if p1 == s1 ** 2 or p2 == s2 ** 2:
					c += 1
			else:
				c += 1
		return c


class Solution:

	def checkFib(self, arr: list, N: int) -> int:
		from typing import Iterator

		def fibonacci(n: int) -> Iterator[int]:
			(x1, x2) = (0, 1)
			while x1 <= n:
				yield x1
				(x1, x2) = (x2, x1 + x2)
		maximum = float('-inf')
		for i in range(N):
			if arr[i] > maximum:
				maximum = arr[i]
		count = 0
		fibonacci_numbers = list(fibonacci(maximum))
		for i in range(N):
			if arr[i] in fibonacci_numbers:
				count += 1
		return count


class Solution:

	def checkFib(self, arr, N):
		m = max(arr)
		x = [0, 1]
		a = 0
		while a <= m:
			a = x[-1] + x[-2]
			if a > m:
				break
			x.append(a)
		c = 0
		for i in arr:
			if i in x:
				c = c + 1
		return c


class Solution:

	def checkFib(self, arr, N):
		s = 0
		prev = 1
		count = 0
		mp = {}
		maxele = max(arr)
		for i in range(n):
			if arr[i] in mp:
				mp[arr[i]] += 1
			else:
				mp[arr[i]] = 1
		while maxele >= s:
			if s in mp and mp[s] > 0:
				count += mp[s]
			mp[s] = 0
			s += prev
			prev = s - prev
		return count


class Solution:

	def checkFib(self, arr, N):
		s = {0, 1}
		m = max(arr)
		a = 0
		b = 1
		c = 0
		while c <= m:
			c = a + b
			s.add(c)
			a = b
			b = c
		count = 0
		for elem in arr:
			if elem in s:
				count += 1
		return count


class Solution:

	def checkFib(self, arr, N):
		f = [0, 1]
		count = 0
		if 0 in arr:
			count += arr.count(0)
		i = 2
		nu = 1
		while nu <= max(arr):
			nu = f[i - 1] + f[i - 2]
			f.append(nu)
			if nu in arr:
				num = arr.count(nu)
				count += num
			i += 1
		return count
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]


class Solution:

	def checkFib(self, arr, N):
		(f1, f2) = (0, 1)
		l = [0, 1]
		len = 1
		while f2 < max(arr):
			f3 = f1 + f2
			l.append(f3)
			f1 = f2
			f2 = f3
		count = 0
		for i in arr:
			if i in l:
				count += 1
		return count


class Solution:

	def checkFib(self, arr, N):
		a = []
		a.append(0)
		a.append(1)
		i = 2
		j = 1
		c = 0
		while j < max(arr):
			j = a[i - 1] + a[i - 2]
			a.append(j)
			i += 1
		for i in arr:
			if i in a:
				c += 1
		return c


class Solution:

	def checkFib(self, arr, N):
		m = max(arr)
		l = [0, 1]
		while l[-1] < m:
			l.append(l[-1] + l[-2])
		c = 0
		for i in arr:
			if i in l:
				c += 1
		return c


class Solution:

	def checkFib(self, arr, N):
		sum = 0
		l = []
		l.append(0)
		l.append(1)
		i = 2
		j = 1
		while j < max(arr):
			j = l[i - 1] + l[i - 2]
			l.append(j)
			i += 1
		count = 0
		for i in arr:
			if i in l:
				count += 1
		return count


from math import sqrt

class Solution:

	def isPerfectSquare(self, x):
		s = int(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 checkFib(self, arr, N):
		count = 0
		for i in arr:
			if self.isFibonacci(i):
				count += 1
		return count


import math

class Solution:

	def isPrefect(self, num):
		x = int(math.sqrt(num))
		return x * x == num

	def checkFib(self, arr, N):
		count = 0
		for i in range(0, N):
			if self.isPrefect(5 * arr[i] * arr[i] + 4) or self.isPrefect(5 * arr[i] * arr[i] - 4):
				count += 1
		return count


import math

class Solution:

	def isFibb(self, num):
		val = 5 * num * num - 4
		i = int(math.sqrt(val))
		if i * i == val:
			return True
		val = 5 * num * num + 4
		i = int(math.sqrt(val))
		if i * i == val:
			return True
		return False

	def checkFib(self, arr, N):
		count = 0
		for num in arr:
			if num == 0:
				count += 1
			elif self.isFibb(num):
				count += 1
		return count


import math

class Solution:

	def isPerfectSquare(self, num):
		n = int(math.sqrt(num))
		return n * n == num

	def checkFib(self, arr, N):
		count = 0
		for i in range(N):
			if self.isPerfectSquare(5 * arr[i] * arr[i] + 4) or self.isPerfectSquare(5 * arr[i] * arr[i] - 4):
				count += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		ob = Solution()
		ans = ob.checkFib(a, n)
		print(ans)


class Solution:

	def checkFib(self, arr, N):
		i = 1
		f1 = 0
		f2 = 1
		l = []
		if 0 in arr:
			l.append(0)
		f3 = 0
		while f3 <= max(arr):
			f3 = f1 + f2
			f1 = f2
			f2 = f3
			l.append(f3)
			i = i + 1
		l1 = []
		for i in arr:
			if i in l:
				l1.append(i)
		return len(l1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		ob = Solution()
		ans = ob.checkFib(a, n)
		print(ans)


class Solution:

	def checkFib(self, arr, N):
		count = 0
		list1 = []
		n1 = 0
		list1.append(n1)
		n2 = 1
		list1.append(n2)
		i = 2
		while list1[-1] <= max(arr):
			n3 = n1 + n2
			list1.append(n3)
			i += 1
			n1 = n2
			n2 = n3
		for i in arr:
			if i in list1:
				count += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		ob = Solution()
		ans = ob.checkFib(a, n)
		print(ans)


class Solution:

	def checkFib(self, arr, N):
		d = max(arr)
		l = [0, 1, 1]
		while l[-1] <= d:
			l.append(l[-1] + l[-2])
		c = 0
		for i in arr:
			if i in l:
				c += 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		ob = Solution()
		ans = ob.checkFib(a, n)
		print(ans)


class Solution:

	def checkFib(self, arr, N):
		fib = [0, 1]
		itr = 0
		k = max(arr)
		num = fib[0] + fib[1]
		while num <= k:
			num = fib[itr] + fib[itr + 1]
			fib.append(num)
			itr += 1
		fib.pop()
		fib = list(set(fib))
		count = 0
		for itr in range(len(fib)):
			if fib[itr] in arr:
				count += arr.count(fib[itr])
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		ob = Solution()
		ans = ob.checkFib(a, n)
		print(ans)


class Solution:

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


import math

def isPerfectSquare(num):
	n = int(math.sqrt(num))
	return n * n == num

class Solution:

	def checkFib(self, arr, N):
		cnt = 0
		for i in range(N):
			num1 = 5 * arr[i] * arr[i] + 4
			num2 = 5 * arr[i] * arr[i] - 4
			if isPerfectSquare(num1) or isPerfectSquare(num2):
				cnt += 1
		return cnt


class Solution:

	def checkFib(self, arr, N):
		import math

		def is_fibonacci(num):
			x = int(math.sqrt(num))
			return x * x == num
		ans = 0
		for i in arr:
			if is_fibonacci(i ** 2 * 5 + 4) or is_fibonacci(i ** 2 * 5 - 4):
				ans += 1
		return ans


class Solution:

	def checkFib(self, arr, N):
		s = set()
		k = max(arr)
		i = 0
		j = 1
		s.add(i)
		while j < k:
			temp = i + j
			s.add(temp)
			i = j
			j = temp
		ans = 0
		for x in arr:
			if x in s:
				ans += 1
		return ans


from math import sqrt

class Solution:

	def checkFib(self, arr, n):
		c = 0
		for x in arr:
			num1 = 5 * x * x + 4
			num2 = abs(5 * x * x - 4)
			s1 = int(sqrt(num1))
			s2 = int(sqrt(num2))
			if s1 * s1 == num1 or s2 * s2 == num2:
				c += 1
		return c


class Solution:

	def checkFib(self, arr, N):
		c = 0
		from math import sqrt
		for i in arr:
			n1 = 5 * i * i + 4
			n2 = abs(5 * i * i - 4)
			s1 = int(sqrt(n1))
			s2 = int(sqrt(n2))
			if s1 * s1 == n1 or s2 * s2 == n2:
				c += 1
		return c


import math

class Solution:

	def checkFib(self, arr, N):
		s = 0
		for i in range(0, N):
			x = 5 * arr[i] * arr[i] - 4
			y = 5 * arr[i] * arr[i] + 4
			if x >= 1:
				if math.ceil(math.sqrt(x)) == math.floor(math.sqrt(x)):
					s += 1
					continue
			if y >= 1:
				if math.ceil(math.sqrt(y)) == math.floor(math.sqrt(y)):
					s += 1
		return s


class Solution:

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

	def checkFib(self, arr, N):
		ans = 0
		for i in arr:
			if self.isPerfectSquare(5 * i * i + 4) or self.isPerfectSquare(5 * i * i - 4):
				ans += 1
		return ans


import math

class Solution:

	def checkFib(self, arr, N):
		c = 0
		for i in arr:
			if 5 * i * i - 4 > 0 and math.sqrt(5 * i * i - 4) % 1 == 0:
				c += 1
				continue
			if 5 * i * i + 4 > 0 and math.sqrt(5 * i * i + 4) % 1 == 0:
				c += 1
		return c