Đếm cặp hợp lệ trong mảng thỏa mãn điều kiện đặc biệt C++

Cho mảng N phần tử. Đếm cặp (i,j) với i

1. arr[i] == arr[j]
2. arr[i] + arr[j] là số chẵn
3. i + j < 120

Ví dụ minh họa

Ví dụ 1:

• Input: Arr = {3, 2, 1, 2, 4, 3}, N = 6
• Output: 2
• Giải thích: (3,3) tại chỉ số (0,5): 3+3=6 chẵn, 0+5=5<120. (2,2) tại (1,3): 2+2=4 chẵn, 1+3=4<120.

Ví dụ 2:

• Input: Arr = {1, 2, 3, 4, 5, 6}, N = 6
• Output: 0
• Giải thích: Không có phần tử trùng lặp.

Mã nguồn C++

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

int countPairs(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 % 2 == 0 && i + j < 120) {
                if (arr[i] == arr[j]) {
                    count++;
                    cout << endl << " a:" << arr[i] << " b:" << arr[j];
                }
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {1, 2, 3, 2, 4, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Valid pairs in array: " << countPairs(arr, n);
    return 0;
}

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

Valid pairs in array:
 a:1 b: 1
 a:2 b: 2
 a:4 b: 4
3

Phân tích điều kiện

• Điều kiện 1: arr[i] == arr[j] → hai phần tử bằng nhau.
• Điều kiện 2: arr[i] + arr[j] chẵn → tự động thỏa nếu điều kiện 1 đúng (2×x luôn chẵn).
• Điều kiện 3: i + j < 120 → chỉ áp dụng khi N lớn.

→ Bài toán thực chất: Đếm cặp chỉ số (i

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

int countPairsOptimized(int arr[], int n) {
    unordered_map> pos;
    for (int i = 0; i < n; i++) {
        pos[arr[i]].push_back(i);
    }
    
    long long count = 0;
    for (auto& [val, indices] : pos) {
        int m = indices.size();
        for (int a = 0; a < m; a++) {
            for (int b = a + 1; b < m; b++) {
                if (indices[a] + indices[b] < 120) count++;
            }
        }
    }
    return count;
}