সমস্যা বিবৃতি
N ধনাত্মক পূর্ণসংখ্যাগুলির একটি অ্যারে দেওয়া, কাজটি হল ক্ষুদ্রতম ধনাত্মক পূর্ণসংখ্যাটি খুঁজে বের করা যা অ্যারের যেকোন দুটি উপাদানের মধ্যে স্থাপন করা যেতে পারে যেমন, সাবয়ারেতে উপাদানগুলির যোগফল ঘটতে থাকা উপাদানগুলির সমষ্টির সমান। এর পরে সাব্যারেতে, নতুন স্থাপন করা পূর্ণসংখ্যার সাথে দুটি সাবয়ারের যে কোনো একটিতে অন্তর্ভুক্ত করা হয়
উদাহরণ
যদি arr ={3, 2, 1, 5, 7, 10} হয় তাহলে আউটপুট হবে 6। যদি আমরা 5 এবং 7-এর মধ্যে মান 6 রাখি তাহলে বাম এবং ডান সাবয়ারের সমষ্টি নিচের মত সমান হবে −
+ 2 + 1 + 5 + 6 =17
7 + 10 =17
অ্যালগরিদম
- সমস্ত অ্যারের যোগফল S দ্বারা ধরা যাক
- ধারণা হল সূচক i পর্যন্ত বাম যোগফল খুঁজে বের করা (এটি সহ)। এই যোগফল L হতে দিন
- এখন সাবয়ারের arri+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
