Số cặp có tổng là lũy thừa của 2 C++

Cho mảng, đếm số cặp có tổng là lũy thừa của 2.

Ví dụ: arr = [1, 2, 3] → 1 cặp (1, 3) vì 1+3=4=2².

Giải thuật

• Khởi tạo count = 0
• Hai vòng lặp lấy mọi cặp
• sum = arr[i] + arr[j]
• Kiểm tra lũy thừa của 2: (sum & (sum - 1)) == 0
• Nếu đúng count++
• Trả về count

Ví dụ minh họa

#include <bits/stdc++.h> 
using namespace std; 

int get2PowersCount(int arr[], int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
        for (int j = i + 1; j < n; j++) { 
            int sum = arr[i] + arr[j]; 
            if ((sum & (sum - 1)) == 0) { count++; } 
        } 
    } 
    return count; 
} 

int main() { 
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
    int n = 10; 
    cout << get2PowersCount(arr, n) << endl; 
    return 0; 
} 

Đầu ra

6