Tìm cặp phần tử hoán đổi để hai mảng có tổng bằng nhau C++

Cho hai mảng A và B với số phần tử khác nhau. Cần tìm cặp (x, y) với x thuộc A, y thuộc B sao cho sau khi hoán đổi x và y, tổng của hai mảng trở nên bằng nhau.

Ví dụ: A = [4, 1, 2, 2, 1, 1] (tổng 11), B = [3, 3, 6, 3] (tổng 15). Cặp (1, 3) khi hoán đổi sẽ cho A = [4, 3, 2, 2, 1, 1] (tổng 13) và B = [1, 3, 6, 3] (tổng 13).

Giải thuật

Duyệt qua tất cả các cặp phần tử từ hai mảng, tính tổng mới của mỗi mảng sau khi hoán đổi, kiểm tra xem hai tổng mới có bằng nhau không.

Ví dụ minh họa

#include <iostream>
using namespace std;

int arraySum(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) sum += arr[i];
    return sum;
}

void getPair(int A[], int n, int B[], int m) {
    int sum_first = arraySum(A, n);
    int sum_second = arraySum(B, m);
    int newsum_first, newsum_second, first, second;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            newsum_first = sum_first - A[i] + B[j];
            newsum_second = sum_second - B[j] + A[i];
            if (newsum_first == newsum_second) {
                first = A[i];
                second = B[j];
            }
        }
    }
    cout << "(" << first << ", " << second << ")";
}

int main() {
    int A[] = {4, 1, 2, 2, 1, 1};
    int n = sizeof(A) / sizeof(A[0]);
    int B[] = {3, 3, 6, 3};
    int m = sizeof(B) / sizeof(B[0]);
    getPair(A, n, B, m);
}

Kết quả

(1, 3)