Đếm cặp trong mảng có tổng là bình phương hoàn hảo C++

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

Ví dụ minh họa

Ví dụ 1:

• Input: Arr = {4, 3, 2, 1, 2, 4}, N = 6
• Output: 2
• Giải thích: Arr[1]+Arr[3]=3+1=4, Arr[2]+Arr[4]=2+2=4. Còn lại tổng 7,6,5,8 không phải bình phương.

Ví dụ 2:

• Input: Arr = {3, 3, 3, 3, 3}, N = 5
• Output: 0
• Giải thích: Mọi cặp tổng = 6, không phải bình phương.

Mã nguồn C++

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

int countPairs(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;
}

int main() {
    int arr[] = {1, 2, 4, 8, 5, 6};
    int n = sizeof(arr) / sizeof(int);
    cout << "Cap co tong la binh phuong hoan hao: " << countPairs(arr, n);
    return 0;
}

Kết quả chạy chương trình

Cap co tong la binh phuong hoan hao: 2

Tối ưu hóa O(n × √M) - Duyệt bình phương

M = giá trị lớn nhất trong mảng. Bình phương lớn nhất ≤ 2M.

1. Đếm tần suất freq[x] của mỗi giá trị.
2. Với mỗi bình phương s = k² (k từ 1 đến √(2M)):
3. Với mỗi x, y = s - x. Nếu y ≥ x và freq[y] > 0:
4. Nếu x == y: cộng C(freq[x], 2).
5. Nếu x < y: cộng freq[x] × freq[y].

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

long long countPairsOptimized(vector& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    unordered_map freq;
    for (int x : arr) freq[x]++;
    
    long long count = 0;
    int maxSum = 2 * maxVal;
    for (int k = 1; k * k <= maxSum; k++) {
        int target = k * k;
        for (auto& [x, cntX] : freq) {
            int y = target - x;
            if (y < x) continue;
            auto it = freq.find(y);
            if (it != freq.end()) {
                if (x == y) count += 1LL * cntX * (cntX - 1) / 2;
                else count += 1LL * cntX * it->second;
            }
        }
    }
    return count;
}

Độ phức tạp