मान लीजिए हमारे पास एक सरणी A है, जिसमें n तत्व हैं। हमारा कार्य सरणी A को दो उपसरणी में विभाजित करना है, ताकि प्रत्येक उपसरणी का योग समान हो। मान लीजिए सरणी A = [2, 3, 4, 1, 4, 5], आउटपुट 1 है, इसलिए 1 से पहले और बाद की उपसरणी ली जाती हैं: [2, 3, 4], और [4, 5]।
इस समस्या को हल करने के लिए, हम पहले तत्व को छोड़कर पूरी सरणी का योग right_sum में लेंगे। मान लें कि यह विभाजन तत्व है। हम बाएं से दाएं पार करेंगे। right_sum से एक तत्व घटाकर और left_sum में एक तत्व जोड़कर, हम उस बिंदु को लेते हैं जब right_sum = left_sum।
उदाहरण
#include <iostream>
using namespace std;
int getPartitionElement(int arr[], int size) {
int right = 0, left = 0;
for (int i = 1; i < size; i++)
right += arr[i];
for (int i = 0, j = 1; j < size; i++, j++) {
right -= arr[j];
left += arr[i];
if (left == right)
return arr[i + 1];
}
return -1;
}
int main() {
int arr[] = { 2, 3, 4, 1, 4, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Partition element: " << getPartitionElement(arr, size);
}
आउटपुट
Partition element: 1
