在C ++中平均分割数组所需的最小正整数

问题陈述

给定一个由N个正整数组成的数组，任务是找到可以放置在该数组的任何两个元素之间的最小正整数，以使子数组中出现在其之前的元素之和等于出现在其中的元素之和在它之后的子数组中，新放置的整数包含在两个子数组中的任何一个中

示例

如果arr = {3，2，1，5，7，10}，则输出为6。如果我们将值6放在5和7之间，则左子数组和右子数组的总和如下所示-

+ 2 +1 + 5 + 6 = 17

7 + 10 = 17

算法

• 令整个数组的和为S

• 这个想法是找到直到索引i（包括它）的剩余总和。让这个和为L

• 现在，子数组arri + 1 .. N的总和为S –L。令该总和为R

• 由于两个子阵列的总和应该相等，因此，将上述两个总和L和R中的较大者减小为这两个子阵列中较小的总和的值，并且较大的总和与较小的总和之差将是所需的正整数的值。

示例

#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 << "Element " << minValue << " needs to be inserted\n";
   return 0;
}

输出结果

当您编译并执行上述程序时。它产生以下输出-

Element 6 needs to be inserted