Поиск пары чисел, дающие степень // Python

Question

Поиск пары чисел, дающие степень // Python

Дмитрий Трусов Знаток (356), на голосовании 6 дней назад

Дано кол-во элементов списка и список, нужно вывести количество пар, дающих степень 2

Я написал 2 кода, 1 в лоб, другой более оптимальный, но проходит не все тесты, ПОМОГИТЕ

2-ой код

 from collections import Counter 
a=int(input()) 
 
b=list(map(int,input().split())) 
 
g=Counter(b) 
o=set(b) 
v=set(b) 
 
 
tt=0 
for i in o: 
    v.remove(i) 
    for j in v: 
        n=i+j 
        if n & (n-1) == 0: 
             
            tt+=g[i]*g[j] 
     
for i,j in g.items(): 
    if 2*i & (2*i-1) == 0 and j>1: 
        if j!=2: 
            tt+=j 
        else: 
            tt+=1 
         
print(tt)

Answer 1

 from collections import Counter  
a = int(input())  
b = list(map(int, input().split()))  
 
g = Counter(b)  
o = set(b)  
v = set(b)  
 
tt = 0  
# Подсчет пар с разными элементами 
for i in o:  
    v.remove(i)  
    for j in v:  
        n = i + j  
        if n & (n-1) == 0 and n > 0: # Проверка на степень 2 
            tt += g[i] * g[j]  
     
# Подсчет пар с одинаковыми элементами     
for i, j in g.items():  
    if 2*i & (2*i-1) == 0 and 2*i > 0 and j > 1: # Проверка на степень 2 
        tt += j * (j - 1) // 2 # Комбинаторная формула для подсчета пар 
         
print(tt)

Answer 2

Jurijus Zaksas Искусственный Интеллект (467304) 1 месяц назад

Что такое "пара, дающая степень 2" чисто математически?

Дмитрий ТрусовЗнаток (356) 1 месяц назад

a i + a j = 2 ^ n
n - целое число

Jurijus Zaksas Искусственный Интеллект (467304) Так это сумма дает степень, а не пара. Ша сваяем.

Jurijus ZaksasИскусственный Интеллект (467304) 1 месяц назад

 from math import log2 
 
def IsPower2(x): 
    if x<=0: 
        return False 
    return  2**int(log2(x))==x 
 
def FindPow2Sums(a): 
    result = [] 
    for x in a: 
        for y in a: 
            if (x < y and IsPower2(x+y)): 
                result.append([x,y]) 
    return result 
 
print(FindPow2Sums([-1,0,1,2,3,4,5]))