หาคู่สมาชิกที่สลับกันแล้วทำให้ผลรวมของสองอาร์เรย์เท่ากัน C++

ปัญหา

ให้สองอาร์เรย์ A และ B ที่มีจำนวนสมาชิกต่างกัน ต้องการหาคู่ (x, y) โดย x อยู่ใน A และ y อยู่ใน B ที่เมื่อสลับค่าทั้งสองแล้ว ผลรวมของทั้งสองอาร์เรย์จะเท่ากัน

ตัวอย่าง: A = [4, 1, 2, 2, 1, 1] (ผลรวม = 11), B = [3, 3, 6, 3] (ผลรวม = 15)
คู่ที่ต้องการคือ (1, 3) หลังสลับ: A = [4, 3, 2, 2, 1, 1] (ผลรวม = 13), B = [1, 3, 6, 3] (ผลรวม = 13)

วิธีแก้ปัญหา

ใช้วิธี Brute Force ตรวจสอบทุกคู่ที่เป็นไปได้:

1. คำนวณผลรวมของอาร์เรย์ทั้งสอง (sum_first, sum_second)
2. วนลูปตรวจสอบทุกคู่ (A[i], B[j])
3. คำนวณผลรวมใหม่หลังสลับ: newsum_first = sum_first - A[i] + B[j], newsum_second = sum_second - B[j] + A[i]
4. ถ้า newsum_first == newsum_second พบคำตอบ

ความซับซ้อนเวลา: O(n × m)

ตัวอย่างโค้ด C++

#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);
    return 0;
}

ผลลัพธ์

(1, 3)