Interview Question: Count pairs with given sum C++
Company Interviews Using C++ Data Structures and Algorithms
int getPairsCount(int arr[], int n, int k) {
int left = 0;
int right = n - 1;
int count = 0;
while (left <= right) {
if (arr[left] + arr[right] == k) {
count++;
} else if (arr[left] + arr[right] > k) {
right--;
} else {
left++;
}
}
return count;
}English :
This C++ code defines a function called `getPairsCount` that takes an array `arr` of integers, its length `n`, and an integer `k` as input parameters. The purpose of this function is to find and count the pairs of elements in the array whose sum equals the given value `k`. Here’s a step-by-step explanation of how the code works:
1. `int left = 0;` and `int right = n — 1;` initialize two pointers, `left` and `right`, to the first and last elements of the array, respectively. These pointers will be used to traverse the array.
2. `int count = 0;` initializes a variable `count` to zero. This variable will be used to keep track of the count of pairs that sum up to `k`.
3. The code enters a `while` loop that continues as long as `left` is less than or equal to `right`. This loop is used to traverse the array and check pairs.
4. Inside the loop, it checks if the sum of the elements pointed to by `left` and `right` is equal to `k` using the condition `arr[left] + arr[right] == k`. If this condition is true, it means that a pair has been found that sums up to `k`, so `count` is incremented by 1 using `count++`.
5. If the sum of the elements is greater than `k`, it means that the sum is too large, and it’s impossible to find a pair with a smaller sum, so the `right` pointer is moved one step to the left by decrementing it with `right — `.
6. If the sum of the elements is less than `k`, it means that the sum is too small, and it’s impossible to find a pair with a larger sum, so the `left` pointer is moved one step to the right by incrementing it with `left++`.
7. The loop continues until the `left` pointer becomes greater than the `right` pointer. At this point, all possible pairs in the array have been checked, and the function exits the loop.
8. Finally, the function returns the value of `count`, which represents the count of pairs in the array whose sum is equal to `k`.
In summary, this code efficiently finds and counts pairs in the given array that sum up to the target value `k` by using a two-pointer approach. The pointers start from the extremes of the array and move towards each other as the algorithm iterates through the array. This approach has a time complexity of O(n) and is a common technique for solving this type of problem.
Hindi :
यह C++ कोड एक फ़ंक्शन `getPairsCount` को परिभाषित करता है जो एक इंटीज़ एरे `arr`, उसकी लम्बाई `n`, और एक पूर्णांक `k` को इनपुट पैरामीटर के रूप में लेता है। इस फ़ंक्शन का उद्देश्य एरे में उन तोड़ों की तलाश और गिनती करना है जिनके योग का मान दिया गया मूल्य `k` के बराबर है। निम्नलिखित कोड काम करने की प्रक्रिया की स्टेप-बाई-स्टेप व्याख्या यहाँ दी गई है:
1. `int left = 0;` और `int right = n — 1;` `left` और `right` नामक दो पॉइंटर्स को पहले और अंतिम तत्वों के रूप में इनिशियलाइज़ करता है, ये पॉइंटर्स एरे को ट्रावर्स करने के लिए उपयोग किए जाएंगे।
2. `int count = 0;` एक चर `count` को शून्य से शुरू करता है। इस चर का उपयोग तोड़ों की गिनती करने के लिए किए जाने वाले गिनती करने के लिए किए जाने वाले गिनती करने के लिए किया जाएगा जिनका योग `k` के बराबर होता है।
3. कोड एक `while` लूप में प्रवेश करता है जो तब तक चलता है जब तक `left` `right` से कम या बराबर है। इस लूप का उपयोग एरे को ट्रावर्स करने और तोड़ों की जांच करने के लिए किया जाता है।
4. लूप के अंदर, यह चेक करता है कि `left` और `right` द्वारा पॉइंट किए जाने वाले तत्वों का योग `k` के बराबर है इस शर्त का उपयोग करके `arr[left] + arr[right] == k`। यदि यह शर्त सत्य होती है, तो इसका मतलब है कि एक तोड़ा मिल गया है जिसका योग `k` के बराबर होता है, इसके बाद `count` को `count++` का उपयोग करके 1 से बढ़ा दिया जाता है।
5. यदि तत्वों का योग `k` से अधिक होता है, तो इसका मतलब है कि योग बहुत बड़ा है, और एक तोड़ा छोटे योग के साथ नहीं मिल सकता है, इसलिए `right` पॉइंटर को `right — ` का उपयोग करके बाईं ओर एक कदम आगे बढ़ा दिया जाता है।
6. यदि तत्वों का योग `k` से कम होता है, तो इसका मतलब है कि योग बहुत छोटा है, और एक तोड़ा बड़े योग के साथ नहीं मिल सकता है, इसलिए `left` पॉइंटर को `left++` का उपयोग करके दाहिनी ओर एक कदम आगे बढ़ा दिया जाता है
।
7. लूप `left` पॉइंटर `right` पॉइंटर से अधिक हो जाने पर जारी रहता है। इस बिंदु पर, एरे में सभी संभावित तोड़े की जांच हो चुकी है, और फ़ंक्शन लूप से बाहर निकलता है।
8. अंत में, फ़ंक्शन `count` के मान को लौटाता है, जिसका मतलब है कि एरे में उन तोड़ों की गिनती करता है जिनका योग `k` के बराबर होता है।
संक्षेप में, यह कोड इस समस्या को हल करने के लिए एरे में तोड़ों को खोजने और गिनने के लिए दो-पॉइंटर दृष्टिकोण का उपयोग करके लक्ष्य मूल्य `k` के बराबर जोड़ता है। पॉइंटर एरे के दोनों किनारों से शुरू होते हैं और जैसे-जैसे एल्गोरिदम एरे में चलता है, वे एक दूसरे की ओर बढ़ते हैं। इस दृष्टिकोण का समय संवादन का ओ(n) होता है और इस प्रकार की समस्या को हल करने के लिए एक सामान्य तकनीक है।
Hinglish :
Is C++ code mein ek function `getPairsCount` ko define kiya gaya hai jo ek integer array `arr`, uski length `n`, aur ek integer `k` ko input parameters ke roop mein le leta hai. Is function ka maksad yah hai ki yah array mein un dono elements ke pairs ko khojkar ginte hai jinke yog ke barabar di gayi mulya `k` ke barabar hota hai. Yahaan ek kadam-se-kadam vyakhya di gayi hai ki yah code kaise kaam karta hai:
1. `int left = 0;` aur `int right = n — 1;` pehle aur aakhri tathyon ko darust karne ke liye `left` aur `right` do pointer ko shuruaat mein initialize karte hain. Ye pointer array ko traverse karne ke liye istemal honge.
2. `int count = 0;` ek variable `count` ko shunya se shuruwat karta hai. Is variable ka upayog `k` ke barabar hone wale todon ki ginti ko rakne ke liye kiya jayega.
3. Code ek `while` loop mein pravesh karta hai jo tab tak chalta hai jab tak `left` `right` se kam ya barabar hota hai. Is loop ka upayog array ko traverse karne aur tondon ki jaanch karne ke liye hota hai.
4. Loop ke andar, yah dekhta hai ki `left` aur `right` dvara point kiye gaye tathvon ke yog `k` ke barabar hai ya nahi, `arr[left] + arr[right] == k` shart ka upayog karke. Agar yah shart sach hoti hai, to iska matlab hai ki ek aisa tod mil gaya hai jiska yog `k` ke barabar hota hai, isliye `count` ko `count++` ka upayog karke ek se badhaya jata hai.
5. Agar tathvon ka yog `k` se adhik hota hai, to iska matlab hai ki yog bahut bada hai, aur chhota yog wale tod ko dhoondna sambhav nahi hai, isliye `right` pointer ko `right — ` ka upayog karke ek kadam baayein le jata hai.
6. Agar tathvon ka yog `k` se kam hota hai, to iska matlab hai ki yog bahut chhota hai, aur bada yog wale tod ko dhoondna sambhav nahi hai, isliye `left` pointer ko `left++` ka upayog karke ek kadam daayein le jata hai.
7. Loop `left` pointer `right` pointer se adhik ho jane tak jari rahta hai. Is bindu par, array mein sambhav tondon ki jaanch ho chuki hai, aur function loop se bahar nikalta hai.
8. Ant mein, function `count` ke mulya ko vapas karta hai, jo array mein `k` ke barabar hone wale todon ki ginti ko pradarshit karta hai.
Samanya roop se, yah code di gayi array mein lakshya mulya `k` ke barabar hone wale todon ko khojkar ginti karta hai aur iske liye do-pointer pristhiti ka upayog karta hai. Pointer array ke kinaron se shuru hoti hai aur algorithmya array ko traverse karte samay ek-dusre ki or badhti hai. Is pristhiti ka samay complexity O(n) hota hai aur is prakar ki samasya ka samadhan karne ke liye ek sadharan takneek hai.
