help me solve this

general
1

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.

2

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
3

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