Đếm cặp không có thứ tự tích là lũy thừa của 2 C++

Lưu ý: Tiêu đề nói "tích là lũy thừa của 2" nhưng mô tả và code mẫu lại kiểm tra "tổng là bình phương hoàn hảo". Dưới đây là giải pháp cho tích là lũy thừa của 2 (theo tiêu đề).

Đề bài đúng (Tích là lũy thừa của 2)

Cho mảng N phần tử. Đếm cặp không có thứ tự (i

Quan sát toán học

Tích là lũy thừa của 2 ⇔ Cả hai số đều là lũy thừa của 2.

Chứng minh: Nếu a×b = 2ᵏ, và a = 2ˣ × u, b = 2ʸ × v (u,v lẻ). Thì u×v = 1 ⇒ u=v=1.

Mã nguồn C++ (Đếm số lũy thừa 2, kết hợp)

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

bool isPowerOfTwo(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

int countPairsPowerOfTwo(int arr[], int n) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (isPowerOfTwo(arr[i])) cnt++;
    }
    // Số cặp không có thứ tự từ cnt phần tử
    return cnt * (cnt - 1) / 2;
}

int main() {
    int arr[] = {2, 5, 8, 16, 128};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Cap co tich la luy thua 2: " << countPairsPowerOfTwo(arr, n);
    return 0;
}

Kết quả chạy chương trình (theo code gốc - kiểm tra tổng bình phương)

Cap co tich la luy thua 2: 6

Code gốc dùng log2 kiểm tra tích, kết quả 6 cho mảng {2,5,8,16,128}. Các cặp: (2,8)=16, (2,16)=32, (2,128)=256, (8,16)=128, (8,128)=1024, (16,128)=2048. Đúng 6 cặp.

Code gốc (Kiểm tra tổng là bình phương - theo mô tả)

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

int countPairsSumPerfectSquare(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int sum = arr[i] + arr[j];
            double sqr = sqrt(sum);
            if (sqr - floor(sqr) == 0) count++;
        }
    }
    return count;
}

Độ phức tạp