I’ve successfully solved this problem (CodeChef: Practical coding for everyone). But I wanted to solve this problem using yet another method. I thought that a merge sort type approach can work for this problem as we did in inversion count. So I partition the array in two halves. Find variation count for each half and the final sorted array when merging. Then return the result. But it provides me a WA judgment. Can somebody point out where am I being mistaken? Check method solve3(). Link: https://pastebin.com/7FW876kA.
@arita_roy, I have also thought the same as you. But I am also getting WA. Don’t know where am I wrong?
private static int merge(int[] arr, long k, int start, int mid, int end) {
int count = 0;
ArrayList left = new ArrayList<>();
ArrayList right = new ArrayList<>();
ArrayList result = new ArrayList<>();for (int i = start; i <= mid; i++) { left.add(arr[i]); } for (int i = mid + 1; i <= end; i++) { right.add(arr[i]); } int i = 0, j = 0; // 2,3 1 while (i < left.size() && j < right.size()) { if (left.get(i) > right.get(j)) { result.add(right.get(j)); if (Math.abs(left.get(i) - right.get(j)) >= k) { count += Math.abs(left.size() - i); } j++; } else { result.add(left.get(i)); if (Math.abs(left.get(i) - right.get(j)) >= k) { count += Math.abs(right.size() - j); } i++; } } if (i != left.size()) { while (i != left.size()) { result.add(left.get(i)); i++; } } if (j != right.size()) { while (j != right.size()) { result.add(right.get(j)); j++; } } for (int j2 = 0; j2 < result.size(); j2++) { arr[j2 + start] = result.get(j2); } return count; }
I don’t know about your logic. But if someone finds wrong in this. Please comment.