सी ++ में सरणी में संभावित चाल के बाद बाएं सूचक की अनुक्रमणिका पाएं

इस समस्या में, हमें आकार N का एक सरणी arr[] दिया जाता है। हमारा कार्य सरणी में संभावित चालों के बाद बाएँ सूचक की अनुक्रमणिका ढूँढना है ।

हमारे पास ऐरे के लिए दो पॉइंटर्स हैं, एक लेफ्ट पॉइंटर और दूसरा राइट पॉइंटर।

लेफ्ट पॉइंटर इंडेक्स 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.

समाधान दृष्टिकोण

समस्या का एक सरल समाधान है लेफ्टपॉइंटर और राइटपॉइंटर को रकम के आधार पर ले जाना। और फिर जांचें कि क्या लेफ्टपॉइंटर राइटपॉइंटर से एक बड़ा है।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#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