This is my code for counting inverrsion pair i have modified the logic from counting inversion pairs but it is not working could you please point out why?
int cnt = 0;
void merge(vector<int> &a, int low, int mid, int high) {
vector<int> temp;
int left = low;
int right = mid + 1;
while (left <= mid && right <= high) {
if (a[left] <= a[right]) {
temp.push_back(a[left]);
left++;
} else {
if (a[left] > 2 * a[right] && left <right) {
cnt += mid - left + 1;
}
temp.push_back(a[right]);
right++;
}
}
while (left <= mid) {
temp.push_back(a[left]);
left++;
}
while (right <= high) {
temp.push_back(a[right]);
right++;
}
for (int i = low; i <= high; i++) {
a[i] = temp[i - low];
}
for (int i = low; i <= high; i++) {
cout << a[i] << " ";
}
cout << cnt << endl;
}
void mergesort(vector<int> &a, int low, int high) {
if (low >= high)
return;
int mid = low + (high - low) / 2;
mergesort(a, low, mid);
mergesort(a, mid + 1, high);
merge(a, low, mid, high);
}
int team(vector<int> &a, int n) {
mergesort(a, 0, n - 1);
return cnt;
}
why is this not working the answer for the testcase 4 1 2 3 1 is 3 is am getting 2 in this code ?
New contributor
Ramya Shah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.