*Inversion Count*for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.

Formal solution to solve is:

Given is an array

*A*of

*N*integers. Inversion is a pair of indexes

*(P, Q)*such that

*P < Q*and

*A[Q] < A[P]*.

Write a function

`class Solution { public int array_inversion_count(int[] A); }`

which computes the number of inversions in

*A*, or returns

*-1*if such number exceeds

*1,000,000,000*.

Assume that:

N is an integer within the range

*[0..100,000]*;

each element of array A is an integer within the range

*[-2,147,483,648..2,147,483,647]*.

For example, in the following array

*A[0] = -1 A[1] = 6 A[2] = 3*

*A[3] = 4 A[4] = 7 A[5] = 4*

there are four inversions:

*(1,2) (1,3) (1,5) (4,5)*

so the function should return

*4*.

Complexity:

expected worst-case time complexity is

*O(N*log(N))*;

expected worst-case space complexity is

*O(N)*, beyond input storage (not counting the storage required for input arguments).

`import java.math.*;`

class Solution {

public int array_inversion_count ( int[] A ) {

// write your code here

int n = A.length;

int counter = 0;

for(int p = 0; p < n - 1; p++)

` { `

` for(int q = p+1; q < n; q++) `

` { `

` if( A[p] > A[q] ) counter++;`

}

}

return counter;

}

}

can you convert this to either Javascript, Python or Objective-c?

ReplyDeleteNo problem, javascript code should look very similar. I will assign it. Regarding Python, I do not know it, sorry. I can also post C/C++ code if it can help you, I don't know if Objective-c has much different syntax :)

DeleteHere, worst case of time complexity is O(n^2).

ReplyDeleteyou code is good.

Code you have posted has running time of O(n^2) not O(n.logn)

ReplyDelete