Số nguyên dương nhỏ nhất cần chèn để chia mảng thành hai phần bằng nhau trong C++

Đề bài

Cho mảng N số nguyên dương, nhiệm vụ là tìm số nguyên dương nhỏ nhất có thể đặt giữa bất kỳ hai phần tử nào của mảng sao cho tổng các phần tử trong mảng con trước nó bằng tổng các phần tử trong mảng con sau nó, với số nguyên mới được chèn bao gồm trong một trong hai mảng con.

Ví dụ

Nếu arr = {3, 2, 1, 5, 7, 10} thì đầu ra là 6. Nếu đặt giá trị 6 giữa 5 và 7 thì tổng mảng con trái và phải bằng nhau như sau −

3 + 2 + 1 + 5 + 6 = 17

7 + 10 = 17

Thuật toán

• Gọi tổng của toàn bộ mảng là S
• Ý tưởng là tìm tổng bên trái đến chỉ số i (kể cả i). Gọi tổng này là L
• Tổng của mảng con arr[i+1 .. N] là S - L. Gọi tổng này là R
• Vì tổng của hai mảng con nên bằng nhau, tổng lớn hơn trong hai tổng L và R nên được giảm xuống giá trị của tổng nhỏ hơn, và hiệu giữa tổng lớn và tổng nhỏ sẽ là giá trị số nguyên dương cần thiết.

Ví dụ

#include <iostream>
#include <numeric>
#include <climits>
using namespace std;
int getMinimumSplitPoint(int *arr, int n) {
    int sum = 0;
    sum = accumulate(arr, arr + n, sum);
    int leftSum = 0;
    int rightSum = 0;
    int minValue = INT_MAX;
    for (int i = 0; i < n - 1; ++i) {
        leftSum += arr[i];
        rightSum = sum - leftSum;
        if (leftSum > rightSum) {
            int e = leftSum - rightSum;
            if (e < minValue) {
                minValue = e;
            }
        } else {
            int e = rightSum - leftSum;
            if (e < minValue) {
                minValue = e;
            }
        }
    }
    return minValue;
}
int main() {
    int arr[] = {3, 2, 1, 5, 7, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int minValue = getMinimumSplitPoint(arr, n);
    cout << "Phần tử " << minValue << " cần được chèn\n";
    return 0;
}

Kết quả

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:

Phần tử 6 cần được chèn