Calculating the number of inversions in a sequence required to arrange it in increasing order

Question

The input is of the form

5
2 3 9 2 9

The output should be the number of inversions that should be done to arrange the sequence in order from smallest to greatest. i.e the new sequence would be 2 2 3 9 9 and to produce this from the input 2 inversions were made.

So basically what I think I need to do is, convert the input into an array and then run the following code

k = int(input())
str = input()
def getInvCount(arr, n):

inv_count = 0
for i in range(n):
    for j in range(i + 1, n):
        if (arr[i] > arr[j]):
            inv_count += 1

return inv_count

arr = str.split() 
n = len(arr)
print(getInvCount(arr, n))

Alternatively I even tried this code

k = int(input())
def mergeSort(arr, n):

temp_arr = [0]*n
return _mergeSort(arr, temp_arr, 0, n-1)

def _mergeSort(arr, temp_arr, left, right):

inv_count = 0

if left < right:

    mid = (left + right)//2

    inv_count += _mergeSort(arr, temp_arr,
                                left, mid)

    inv_count += _mergeSort(arr, temp_arr,
                              mid + 1, right)

    inv_count += merge(arr, temp_arr, left, mid, right)
return inv_count

def merge(arr, temp_arr, left, mid, right):
i = left
j = mid + 1
k = left
inv_count = 0

while i <= mid and j <= right:

    if arr[i] <= arr[j]:
        temp_arr[k] = arr[i]
        k += 1
        i += 1
    else:
        temp_arr[k] = arr[j]
        inv_count += (mid-i + 1)
        k += 1
        j += 1

while i <= mid:
    temp_arr[k] = arr[i]
    k += 1
    i += 1

while j <= right:
    temp_arr[k] = arr[j]
    k += 1
    j += 1

for loop_var in range(left, right + 1):
    arr[loop_var] = temp_arr[loop_var]
     
return inv_count

str = input()
arr = str.split()
n = len(arr)
result = mergeSort(arr, n)
print(result)

However the first code gets timed out in some cases and the second one fails there. Can I please get some help?

Hello, welcome to StackOverflow. Do you know in which particular case does the second one fail? — Learning Mathematics, Aug 30 '21 at 05:01
Actually this a practice problem where I am able to pass 3 out of the 6 test cases that the website inputs and those cases aren't revealed. — Kevin Karia, Aug 30 '21 at 05:33
Glad it helps. You could also accept the answer by clicking the tick on the left side of my answer to indicate that your doubt has already been resolved and give both you and me some reputation. — Learning Mathematics, Aug 30 '21 at 05:42

score 0 · Accepted Answer · answered Aug 30 '21 at 05:10

You probably forgot to convert your input to int before passing it into mergesort:

k = int(input())
def mergeSort(arr, n):

    temp_arr = [0]*n
    return _mergeSort(arr, temp_arr, 0, n-1)

def _mergeSort(arr, temp_arr, left, right):

    inv_count = 0

    if left < right:

        mid = (left + right)//2

        inv_count += _mergeSort(arr, temp_arr,
                                    left, mid)

        inv_count += _mergeSort(arr, temp_arr,
                                  mid + 1, right)

        inv_count += merge(arr, temp_arr, left, mid, right)
    return inv_count

def merge(arr, temp_arr, left, mid, right):
    i = left
    j = mid + 1
    k = left
    inv_count = 0

    while i <= mid and j <= right:

        if arr[i] <= arr[j]:
            temp_arr[k] = arr[i]
            k += 1
            i += 1
        else:
            temp_arr[k] = arr[j]
            inv_count += (mid-i + 1)
            k += 1
            j += 1

    while i <= mid:
        temp_arr[k] = arr[i]
        k += 1
        i += 1

    while j <= right:
        temp_arr[k] = arr[j]
        k += 1
        j += 1

    for loop_var in range(left, right + 1):
        arr[loop_var] = temp_arr[loop_var]
         
    return inv_count

str = input()
arr = list(map(int, str.split()))
n = len(arr)
result = mergeSort(arr, n)
print(result)

Calculating the number of inversions in a sequence required to arrange it in increasing order

1 Answers1