এই সমস্যায়, আমাদের N আকারের একটি অ্যারে অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল অ্যারেতে সম্ভাব্য স্থানান্তরের পরে বাম পয়েন্টারের সূচী খুঁজে বের করা .
আমাদের অ্যারের জন্য দুটি পয়েন্টার রয়েছে, একটি বাম পয়েন্টার এবং আরেকটি ডান পয়েন্টার৷
বাম পয়েন্টার সূচক 0 থেকে শুরু হয় এবং মান বৃদ্ধি করা হয়।
ডান পয়েন্টার ইনডেক্স (n-1) থেকে শুরু হয় এবং মান হ্রাস পায়।
একটি পয়েন্টারের মান বৃদ্ধি পায় যদি অতিক্রম করা যোগফল অন্যের থেকে কম হয়, যেমন বাম পয়েন্টারের যোগফল ডান পয়েন্টারের যোগফলের থেকে কম হলে, বাম পয়েন্টার বাড়ানো হয় অন্যথায় ডান পয়েন্টারটি হ্রাস পায়। এবং যোগফল আপডেট করা হয়।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : arr[] = {5, 6, 3, 7, 9, 4}
Output : 2 ব্যাখ্যা −
leftPointer = 0 -> sum = 5, rightPointer = 5 -> sum = 4. Move rightPointer leftPointer = 0 -> sum = 5, rightPointer = 4 -> sum = 13. Move leftPointer leftPointer = 1 -> sum = 11, rightPointer = 4 -> sum = 13. Move leftPointer leftPointer = 2 -> sum = 14, rightPointer = 4 -> sum = 13. Move rightPointer leftPointer = 2 -> sum = 14, rightPointer = 3 -> sum = 20. Move rightPointer Position of the left pointer is 2.
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল যোগফলের উপর ভিত্তি করে leftPointer এবং rightPointer সরানো। এবং তারপর লেফটপয়েন্টার রাইটপয়েন্টারের চেয়ে বড় কিনা তা পরীক্ষা করুন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findIndexLeftPointer(int arr[], int n) {
if(n == 1)
return 0;
int leftPointer = 0,rightPointer = n-1,leftPointerSum = arr[0], rightPointerSum = arr[n-1];
while (rightPointer > leftPointer + 1) {
if (leftPointerSum < rightPointerSum) {
leftPointer++;
leftPointerSum += arr[leftPointer];
}
else if (leftPointerSum > rightPointerSum) {
rightPointer--;
rightPointerSum += arr[rightPointer];
}
else {
break;
}
}
return leftPointer;
}
int main() {
int arr[] = { 5, 6, 3, 7, 9, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The index of left pointer after moving is "<<findIndexLeftPointer(arr, n);
return 0;
} আউটপুট
The index of left pointer after moving is 2
