ধরি একটি অ্যারে A আছে যাতে n এলিমেন্ট আছে। আমাদের অ্যারেটি দুটি সাবঅ্যারেতে ভাগ করতে হবে যাতে প্রতিটি সাবঅ্যারের যোগফল সমান হয়। ধরি অ্যারে A = [2, 3, 4, 1, 4, 5], আউটপুট হবে ১, অর্থাৎ ১-এর আগে এবং পরে দুটি সাবঅ্যারে নেওয়া হয়েছে: [2, 3, 4] এবং [4, 5]।
এটি সমাধান করতে আমরা প্রথম এলিমেন্ট বাদে পুরো অ্যারের যোগফল রাইট_সাম (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
