इस समस्या में, हमें आकार N की एक सरणी arr[] दी गई है। हमारा कार्य सरणी में संभावित चालों के बाद बाएं पॉइंटर का इंडेक्स ज्ञात करना है।
सरणी के लिए हमारे पास दो पॉइंटर्स हैं, एक बायां पॉइंटर और दूसरा दायां पॉइंटर।
बायां पॉइंटर इंडेक्स 0 से शुरू होता है और मान बढ़ाया जाता है।
दायां पॉइंटर इंडेक्स (n-1) से शुरू होता है और मान घटाया जाता है।
एक पॉइंटर का मान बढ़ता है यदि पार किया गया योग दूसरे से कम है, यानी यदि बाएं पॉइंटर का योग दाएं पॉइंटर के योग से कम है, तो बायां पॉइंटर बढ़ाया जाता है अन्यथा दायां पॉइंटर घटाया जाता है। और योग अपडेट किए जाते हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट : arr[] = {5, 6, 3, 7, 9, 4} आउटपुट : 2 व्याख्या −
leftPointer = 0 -> योग = 5, rightPointer = 5 -> योग = 4. rightPointer बढ़ाएं leftPointer = 0 -> योग = 5, rightPointer = 4 -> योग = 13. leftPointer बढ़ाएं leftPointer = 1 -> योग = 11, rightPointer = 4 -> योग = 13. leftPointer बढ़ाएं leftPointer = 2 -> योग = 14, rightPointer = 4 -> योग = 13. rightPointer बढ़ाएं leftPointer = 2 -> योग = 14, rightPointer = 3 -> योग = 20. rightPointer बढ़ाएं बाएं पॉइंटर की स्थिति 2 है।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान योग के आधार पर leftPointer और rightPointer को बढ़ाना है। और फिर जांचें कि क्या 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<<"चाल के बाद बाएं पॉइंटर का इंडेक्स है "<<findIndexLeftPointer(arr, n); return 0; } आउटपुट
चाल के बाद बाएं पॉइंटर का इंडेक्स है 2
