সমস্যা বিবরণ
N পজিটিভ ইন্টিজারের একটি অ্যারে দেওয়া আছে। টাস্ক হলো সবচেয়ে ছোট পজিটিভ ইন্টিজার বের করা যেটি অ্যারে-এর যেকোনো দুটি এলিমেন্টের মাঝপথে রাখলে, সেটি মাঝপথে থাকা দুটি সাবঅ্যারে-এর সম সমান হয় (নতুন ইন্টিজারটি যেকোনো একটি সাবঅ্যারেতে থাকবে)।
উদাহরণ
যদি arr = {3, 2, 1, 5, 7, 10} হয়, তবে আউটপুট ৬। যদি ৫ এবং ৭-এর মাঝপথে ৬ রাখা হয়, তবে বাম ও ডান সাবঅ্যারে-এর সম সমান হয়:
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
