एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

Sliding window / Two pointers

ऐरे (array) के साथ काम करते समय, स्लाइडिंग विंडो (Sliding Window) एक लोकप्रिय तकनीक है जो सामान्यतः केवल दो-पॉइंटर्स (Two Pointers) की मदद से समस्याओं को कुशलतापूर्वक हल करती है। इस तकनीक का मूल विचार यह है कि हमारे पास एक बायाँ (left) और एक दायाँ (right) पॉइंटर हो, जिन्हें ज़रूरत पड़ने पर उचित दिशा में खिसकाया जाता है।
Video preview
मान लीजिए हम ऐरे के भीतर एक आदर्श उपखंड (subarray) खोजना चाहते हैं। इसके लिए हम पहले दायें पॉइंटर को जितना संभव हो आगे बढ़ाएँगे, फिर बायें पॉइंटर को समायोजित करने के लिए दाएँ पॉइंटर के पास लाएँगे। इसके बाद, फिर दायें पॉइंटर को आगे बढ़ाएँगे, और दोबारा बायें पॉइंटर को समायोजित करेंगे। हम यह सिलसिला तब तक जारी रखते हैं, जब तक हमें आवश्यकतम उपखंड नहीं मिल जाता। यही प्रक्रिया स्लाइडिंग विंडो कहलाती है।

Challenge - Find two numbers that sum up to k

एक क्रमबद्ध (sorted) ऐरे में n तादाद की संख्याएँ हैं और एक लक्षित मान k दिया गया है। कार्य यह है कि ऐरे की उन दो संख्याओं को खोजें जिनका योग k के बराबर हो। ध्यान दें कि ऐरे में संख्याएँ आरोही क्रम (increasing order) में रखी गई हैं। आपको कोई भी dictionary, maps, hashmap इत्यादि इस्तेमाल करने की अनुमति नहीं है।

Input

इनपुट की पहली पंक्ति में दो पूर्णांक होंगे - n (ऐरे में मौजूद संख्याओं की संख्या, 1 ≤ n ≤ ) और k ()। अगली पंक्ति में n पूर्णांक स्पेस द्वारा अलग-अलग दिए जाएँगे, जो क्रमबद्ध ऐरे के तत्व हैं (), और ये सभी आरोही क्रम में होंगे।

Output

प्रोग्राम को ऐरे की वे दो संख्याएँ प्रिंट करनी चाहिएँ जिनका योग k के बराबर हो। पहली संख्या यथासंभव छोटी होनी चाहिए। यदि ऐसी कोई दो संख्याएँ नहीं मिलतीं, तो प्रोग्राम को Impossible प्रिंट करना चाहिए।

Examples

इनपुट
आउटपुट
5 11 -2 3 4 8 9
3 8
5 1000 -2 3 4 8 9
Impossible

Tutorial

क्योंकि ऐरे पहले से ही आरोही क्रम में है, हम दो पॉइंटर्स की शुरुआत ऐरे के आरंभ (0) और अंत (n-1) पर कर सकते हैं और उनके योग के आधार पर पॉइंटर्स को समायोजित कर सकते हैं।
यदि इन दोनों का योग k से बड़ा हो जाता है, तो दायें पॉइंटर को कम करके देखेंगे। अगर योग k से छोटा है, तो बायें पॉइंटर को बढ़ाएँगे। और यदि योग ठीक k के बराबर हो जाए, तो उन दोनों तत्वों को प्रिंट करके प्रोग्राम को रोक सकते हैं।
n, k = ...                  # n और k को इनिशियलाइज़ करें
a = ...                     # ऐरे को इनिशियलाइज़ करें (यह पहले से क्रमबद्ध है)

l, r = 0, len(a) - 1        # बायें (l) और दायें (r) पॉइंटर्स की शुरुआती स्थिति
while l < r:                # जब तक l और r भिन्न हैं
    if a[l] + a[r] > k:     # अगर योग k से बड़ा है => r को घटाएँ 
        r -= 1
    elif a[l] + a[r] < k:   # अगर योग k से छोटा है => l को बढ़ाएँ
        l += 1
    else:                   # a[l] + a[r] == k => प्रोग्राम रोकें
        print(a[l], a[r])
        break
else:                       # while...else = no-break -> हमें कुछ नहीं मिला
    print('Impossible')
“Two-pointers” एक सामान्य विधि है, जिसका इस्तेमाल कई अलग-अलग परिदृश्यों में किया जा सकता है। इसका मुख्य सिद्धांत है कि सबसे पहले बायें और दायें पॉइंटर्स का शुरुआती स्थान चुनें (जो हर समस्या में भिन्न हो सकता है), और तय करें कि कब और किस तरह पॉइंटर्स को आगे-पीछे करना है (यह नियम भी समस्या के अनुसार अलग-अलग हो सकता है)।
इस उदाहरण में, हमने बायें पॉइंटर को ऐरे की शुरुआत में और दायें पॉइंटर को ऐरे के अंत में रखा है। लेकिन कभी-कभी आपको दायें पॉइंटर की भी शुरुआत ऐरे की शुरुआत से करनी पड़ सकती है, या किसी अन्य स्थिति में, आपको बायें पॉइंटर को ऐरे के अंत से शुरू करके दोनों को आरंभ की ओर खिसकाना पड़ सकता है।
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue