3

I know that the number of inversions in an n-element array can be counted in O(n log(n)) operations using an enhanced merge sort.

However, I came across a different solution, which somehow manages to count the number of inversions in O(n) time, provided that the input is a permutation of (1, 2, 3, ..., n−1, n):

EDIT:-


I am sorry for the code I pasted as it doesn't work in all the cases . Actually this code was used for this question and it passed all the cases . But I am still leaving the code so that it may serve as some intuition and maybe a linear time solution for this problem will come up.

NOTE :- The Below Mentioned Code is Incorrect.


/* int in = 0;
    for (int i = 0; i < n; i++) {
        a[i] = a[i] - i - 1;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] > 0)
            in = in + a[i];
        else if (a[i] < -1)
            in = in - a[i] - 1;
    } */ 

Now the question is can we come up with a linear time solution for this problem ?

12
  • Is that code copied correctly? i being modified in both inner and outer for loops?
    – Mike
    Jun 2, 2014 at 17:25
  • 1
    What exactly is an inversion in this case?
    – bytefire
    Jun 2, 2014 at 17:26
  • An inversion is the case when a[i] > a[j] and i < j. Jun 2, 2014 at 17:28
  • 1
    @Spundum Here is the link to counting inversions by merge sort geeksforgeeks.org/counting-inversions . Jun 2, 2014 at 17:35
  • 1
    @Spundum The merge sort method is a generalized algorithm which will work for any type of array , but the above algorithm is applicable only when the array is a random permutaion of 1,2,3...N. For eg if N =4 . Then array can be 2,4,3,1. Jun 2, 2014 at 17:37

2 Answers 2

3

The obvious answer is that it doesn't. For example, for n = 4 and a = {2, 3, 4, 1}, you code gives the answer 5, even though the correct inversion count is clearly 3.

1

The approach is WRONG! Consider the example below!

int a[] = { 2, 3, 1 };

int in = 0;

for (int i = 0; i < n; i++) {
    a[i] = a[i] - i - 1;
}

// a[] = { 1, 1, -2 };

for (int i = 0; i < n; i++) {
    if (a[i] > 0)
        in = in + a[i];
    else if (a[i] < -1)
        in = in - a[i] - 1;
} 

// in = 1 + 1 - (-1) = 3

The correct answer is 2 but it returns 3 here!

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.