समस्या विवरण
N धनात्मक इंटीजर्स का एक ऐरे दिया गया है, कार्य उस सबसे छोटे धनात्मक पूर्णांक को ढूंढना है जिसे ऐरे के किन्हीं दो एलिमेंट्स के बीच रखा जा सके जैसे कि, उसके पहले आने वाले सबऐरे के एलिमेंट्स का योग, उसके बाद आने वाले सबऐरे के एलिमेंट्स के योग के बराबर हो, नए रखे गए पूर्णांक को दोनों में से किसी एक सबऐरे में शामिल करके।
उदाहरण
यदि arr = {3, 2, 1, 5, 7, 10} तो आउटपुट 6 है। यदि हम मान 6 को 5 और 7 के बीच रखते हैं तो बाएं और दाएं सबऐरे का योग निम्नानुसार बराबर हो जाता है:
3 + 2 + 1 + 5 + 6 = 17
7 + 10 = 17
एल्गोरिदम
- पूरे ऐरे का योग S हो
- विचार इंडेक्स i तक (इसे शामिल करते हुए) लेफ्ट योग ढूंढना है। मान लें यह योग L है
- अब सबऐरे arr[i+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
