Interview Question: Count Inversions Array C++
Company Interviews Using C++ Data Structures and Algorithms
#include <bits/stdc++.h>
using namespace std;
int merge(vector<int> &arr, int low, int mid, int high) {
vector<int> temp; // temporary array
int left = low;
int right = mid + 1;
int cnt = 0;
while (left <= mid && right <= high) {
if (arr[left] <= arr[right]) {
temp.push_back(arr[left]);
left++;
}
else {
temp.push_back(arr[right]);
cnt += (mid - left + 1);
right++;
}
}
while (left <= mid) {
temp.push_back(arr[left]);
left++;
}
while (right <= high) {
temp.push_back(arr[right]);
right++;
}
for (int i = low; i <= high; i++) {
arr[i] = temp[i - low];
}
return cnt;
}
int mergeSort(vector<int> &arr, int low, int high) {
int cnt = 0;
if (low >= high) return cnt;
int mid = (low + high) / 2 ;
cnt += mergeSort(arr, low, mid); // left half
cnt += mergeSort(arr, mid + 1, high); // right half
cnt += merge(arr, low, mid, high); // merging sorted halves
return cnt;
}
int numberOfInversions(vector<int>&a, int n) {
// Count the number of pairs:
return mergeSort(a, 0, n - 1);
}English :
This C++ code implements a function to count the number of inversions in an array using the merge sort algorithm. Inversions in an array are pairs of elements (i, j) such that i < j but arr[i] > arr[j].
Here’s a breakdown of the code:
1. The code starts by including the necessary header files and using the `std` namespace.
2. The `merge` function is defined to merge two sorted subarrays. It takes as input a reference to a vector `arr`, indices `low`, `mid`, and `high`, and it returns the number of inversions in the merged subarray. It uses a temporary vector `temp` to store the merged elements. The `cnt` variable is used to count the number of inversions.
3. The merge process starts by iterating through the left and right halves of the subarray while comparing elements and adding them to `temp` in sorted order. When an element from the right subarray is smaller than an element from the left subarray, it increments the `cnt` variable by the number of elements remaining in the left subarray (Modification 2).
4. After merging the two subarrays into `temp`, the merged elements are transferred back to the original `arr` vector.
5. The `mergeSort` function is a recursive function that sorts the array `arr` using the merge sort algorithm. It takes the `low` and `high` indices as input and returns the total count of inversions.
6. In the `mergeSort` function, the array is divided into two halves, and `mergeSort` is recursively called on each half. The number of inversions from the left and right halves and the number of inversions during merging are added together and returned as the result.
7. The `numberOfInversions` function is a wrapper function that takes a reference to a vector `a` and its size `n`. It simply calls the `mergeSort` function with the appropriate arguments, which sorts the array and counts the inversions. The result is then returned.
In summary, this code uses a modified merge sort algorithm to count the number of inversions in an array efficiently. It does this by recursively dividing the array into smaller subarrays, counting the inversions in each subarray and during the merging process, and returning the total count of inversions.
Hindi :
यह C++ कोड एक फ़ंक्शन का अंगीकरण करता है जो मर्ज सॉर्ट एल्गोरिथम का उपयोग करके एक एरे में उलटने की संख्या को गिनने के लिए किया जाता है। एरे में उलटने के मामले में एकत्र तत्वों (i, j) को इस प्रकार की जोड़ी कहा जाता है कि i < j हो, लेकिन arr[i] > arr[j] हो।
यहां कोड की विस्तारित व्याख्या है:
1. कोड उचित हेडर फ़ाइलों को शामिल करके और `std` नेमस्पेस का उपयोग करके शुरू होता है।
2. `merge` फ़ंक्शन को परिभाषित किया गया है ताकि दो छोटे छोटे अनुश्रेणियों को मिलाया जा सके। इसका इनपुट एक वेक्टर `arr`, सूचकों `low`, `mid`, और `high` का संदर्भ लेता है, और यह मिलाए गए उप-एरिया में उलटने की संख्या को लौटाता है। यह सामयक वेक्टर `temp` का उपयोग मिलाए गए तत्वों को संगठित रूप में सहेजने के लिए करता है। `cnt` चर परिणामी होता है जिसका उपयोग उलटने की संख्या को गिनने के लिए किया जाता है।
3. मर्ज प्रक्रिया इस तरह के तत्वों को मिलाने के दौरान शुरू होती है जब अंश और दाहिनी अंश के मध्य तत्वों का तुलना करके और उन्हें सूचीबद्ध क्रम में `temp` में जोड़ा जाता है। जब दाहिनी उप-एरिया से किसी तत्व का बायाँ उप-एरिया के किसी तत्व से छोटा होता है, तो `cnt` चर को बायाँ उप-एरिया में बचे हुए तत्वों की संख्या से बढ़ा दिया जाता है (संशोधन 2).
4. दो उप-एरियों को `temp` में मिलाने के बाद, मिलाए गए तत्वों को मूल `arr` वेक्टर में पुनः स्थानांतरित किया जाता है।
5. `mergeSort` फ़ंक्शन एक रिकर्सिव फ़ंक्शन है जो मर्ज सॉर्ट एल्गोरिथम का उपयोग करके एरे `arr` को क्रमबद्ध करता है। यह इनपुट के रूप में `low` और `high` सूचकों को लेता है और उलटने की कुल संख्या को लौटाता है।
6. `mergeSort` फ़ंक्शन में, एरे को दो भागों में विभाजित किया जाता है, और प्रत्येक भाग पर रिकर्सिव रूप से `mergeSort` को बुलाया जाता है। बायाँ और दाहिने उप-एरियों से उलटने की संख्या और मर्ज करते समय उलटने की संख्या को मिलाकर पर
िणाम के रूप में लौटाया जाता है।
7. `numberOfInversions` फ़ंक्शन एक वेक्टर `a` और उसका आकार `n` का संदर्भ लेने वाला एक व्रैपर फ़ंक्शन है। यह बस `mergeSort` फ़ंक्शन को उचित तात्कालिकों के साथ बुलाता है, जिससे एरे को क्रमबद्ध किया जाता है और उलटने की संख्या को गिनता है। परिणाम फिर वापस किया जाता है।
संक्षेप में, यह कोड एक संशोधित मर्ज सॉर्ट एल्गोरिथम का उपयोग एक एरे में उलटने की संख्या को प्रभावी रूप से गिनने के लिए करता है। यह इसे एक स्मालर उप-एरियों में विभाजित करके, प्रत्येक उप-एरिया में उलटने की गिनती करके और मर्ज प्रक्रिया के दौरान, उलटने की कुल गिनती को वापस देने के द्वारा करता है।
Hinglish :
Is C++ mein likha gaya code ek function ko implement karta hai jisse merge sort algorithm ka upayog karke ek array mein uljhanon ki ginti karni hai. Array mein uljhan ek prakar ke tatvon (i, j) hote hain jaise ki i < j lekin arr[i] > arr[j].
Yahan ek code ki vistrit vichar hai:
1. Code shuruaat karta hai jaruri header files ko include karke aur `std` namespace ka upayog karke.
2. `merge` function ko do sorted subarrays ko merge karne ke liye define kiya gaya hai. Iska input ek vector `arr`, indices `low`, `mid`, aur `high` ko reference ke roop mein le leta hai, aur yah merged subarray mein uljhanon ki sankhya ko lautata hai. Merged tatvon ko rakhne ke liye temporary vector `temp` ka upayog hota hai. `cnt` variable uljhanon ki sankhya ko gintne ke liye prayukt hota hai.
3. Merge prakriya do subarray ke bayan aur daayan bhagon mein tatvon ka tulnatmak anuroopan karke aur unhein krambaddh kram mein `temp` mein jodkar shuru hoti hai. Jab daayan subarray se ek tatv bayan subarray se kam hota hai, tab `cnt` variable ko bayan subarray mein bache tatvon ki sankhya se badhaya jata hai (Modification 2).
4. Do subarrays ko `temp` mein merge karne ke bad, merged tatv mool `arr` vector mein punah sthanantarit kiye jate hain.
5. `mergeSort` function ek recursive function hai jo array `arr` ko merge sort algorithm ka upayog karke krambaddh karta hai. Iska input `low` aur `high` indices ko leta hai aur uljhanon ki kul sankhya ko lautata hai.
6. `mergeSort` function mein array ko do bhagon mein vibhajit kiya jata hai, aur pratyek bhag par rekursiv roop se `mergeSort` ko bulaya jata hai. Uljhanon ki sankhya bayan aur daayan bhagon se aur merge karne ke dauran ki sankhya ko ek sath joda jata hai aur parinam ke roop mein lautaya jata hai.
7. `numberOfInversions` function ek wrapper function hai jo ek vector `a` aur uska size `n` ka reference leta hai. Yah bas `mergeSort` function ko upayog karta hai sahi pratyukti ke sath, jo array ko krambaddh karta hai aur uljhanon ki ginti karta hai. Parinam fir lautaya jata hai.
Saransh mein, yah code ek sudharit merge sort algorithm ka upayog ek array mein uljhanon ki ginti karne ke liye prabhavi roop se karta hai. Isse yah hota hai ki array ko smller subarrays mein vibhajit kiya jata hai, har subarray mein uljhanon ki ginti ki jati hai aur merge prakriya ke dauran, aur phir uljhanon ki kul ginti ko lautaya jata hai.
