0
import math
#check if a number is fibonacci
def is_fib(n):
    return math.sqrt(5* n**2 + 4 ).is_integer() or math.sqrt(5* n**2 - 4).is_integer()

for i in range(int(input())):
    T = int(input())
    liste = [i for i in map(int,input().split())]
    cnt = 0
    arr = {}
    for i in range(len(liste)):
        for j in range(1,len(liste)):
          if is_fib(liste[i]+liste[j]) and (liste[i]+liste[j] not in arr)  and liste[i] != liste[j]: 
              cnt +=1
              arr[liste[i]+liste[j]] = liste[i]+liste[j]
    print(cnt)

I solved this problem of how many sums of two numbers in a list is a Fibonacci number but I got the time complexity is O(n^2)

How Can I Reduce the time complexity

Soufiane El mazlouzi
  • 11
  • 1
  • 4
    Have you tried reading through the [dozens of posts](https://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence) asking the exact same question? – Cory Kramer Aug 25 '20 at 13:24
  • Does this answer your question? [How to write the Fibonacci Sequence?](https://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence) – Seabody Aug 26 '20 at 05:03

0 Answers0