समस्या कथन
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 है
- चूंकि दो उपसरणियों का योग बराबर माना जाता है, उपरोक्त दो में से बड़ा योग एल और आर, इन दोनों के बीच छोटी राशि के मूल्य और बड़े योग और के बीच के अंतर को घटाया जाना चाहिए छोटा योग, आवश्यक धनात्मक पूर्णांक का मान होगा।
उदाहरण
#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