help me solve this

I need to know what algorithm or methodology can be used to solve this problem.The problem is,

I have an array of integers, which are in some order. how to find the minimum number changes or moves required to convert the array into ascending order.

I am new to competitive programming, So detailed answer would to be great. thanks.

Can you tell us what you mean by moves? If it is swapping with adjacent elements(as given in most problems), then u need to find number of inversions in the array. This can be done using O(n lgn) using BIT or segment tree.

You can also use a modified merge sort as described here http://www.geeksforgeeks.org/counting-inversions/

1 Like

Hi @arvindkr,

Your problem means that you need to find the number of pairs (a[i],a[j]) such that i is less than j, and a[i]>a[j]

for this problem you can Use 2 For loops, and count pairs by O(n*n) time complexity. But it will by sure give you a TLE.

So you need to learn Merge Sort Technique of sorting an array. Merge Sort - Wikipedia

Then after you learn this technique, a little addition of 1 line is required to solve your problem, so you first learn this technique, then again push me a comment. :slight_smile:

Here is the link to my same question and I got understood. Same Question

Thanks. :slight_smile:

1 Like
//