หาค่าที่ต้องบวกเพื่อทำให้อาร์เรย์สมดุล (Balanced) ใน C++

ให้อาร์เรย์ขนาดคู่ (n เป็นเลขคู่) แบ่งเป็น 2 ครึ่ง หาค่าที่ต้องบวกเข้าไป (ที่ครึ่งใดครึ่งหนึ่ง) เพื่อให้ผลรวมทั้งสองครึ่งเท่ากัน

ตัวอย่าง: A = [1, 2, 3, 2, 5, 3] → ครึ่งซ้าย = 1+2+3 = 6, ครึ่งขวา = 2+5+3 = 10 → ต้องบวก 4

อัลกอริทึม

1. คำนวณผลรวมครึ่งซ้าย (0 ถึง n/2 - 1)
2. คำนวณผลรวมครึ่งขวา (n/2 ถึง n-1)
3. คืนค่า |left_sum - right_sum|

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

#include <iostream>
#include <cmath>
using namespace std;

int getValueToBalance(int a[], int n) {
    int left_sum = 0;
    for (int i = 0; i < n/2; i++)
        left_sum += a[i];

    int right_sum = 0;
    for (int i = n/2; i < n; i++)
        right_sum += a[i];

    return abs(left_sum - right_sum);
}

int main() {
    int arr[] = {1, 2, 3, 2, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The number for balancing: " << getValueToBalance(arr, n);
    return 0;
}

ผลลัพธ์

The number for balancing: 4

ความซับซ้อน

เวลา: O(n), พื้นที่: O(1)

ขยายความหมาย

"สมดุล" ในที่นี้หมายถึง ผลรวมครึ่งซ้าย = ผลรวมครึ่งขวา หากต้องการให้สมดุลโดยการย้ายข้อมูลระหว่างครึ่ง จะเป็นปัญหา Partition Problem (NP-Complete)