# Sort number line given as Array by moving an element at ith index by i steps to right

Given an array **arr[]** of **N** integers, the task is to find the minimum number of the moves needed to sort the array in ascending order by moving an element at **i ^{th }**index by

**i**steps to the right in a single move.

Note:In a step, two numbers can lie in the same position.

**Examples:**

Input:N = 4, arr[] = {1, 2, 7, 4}Output:1Explanation:Moving the element at index 3 by 2 steps to the right sorts the array in ascending order in 1 move. Therefore, print 1.

Input:N = 5, arr[] = {2, 5, 8, 1, 9}Output:12Explanation:The most optimal way to arrange the array is: arr[] = {-, -, -, 1, -, -, -,2, -, -, -, -, -, -, -, 5, -, -, -, -, -, -, -, 8, -, -, -, -, -, -, -, -, -, -, -, -,-, -, -, 20}

First arr[0] jumps to index 2, then to index 4, and then to index 7. So Shifting arr[0] will need 3 moves to reach index 7.First arr[1] jumps to index 3, then to index 7, and then to index 15. So Shifting arr[1] will need 3 moves to reach index 15.First arr[2] jumps to index 6, then to index 12, and then to index 24. So Shifting arr[2] will need 3 moves to reach index 23.First arr[4] jumps to index 9, then to index 19, and then to index 39. So Shifting arr[4] will also need 3 moves to reach index 39.

Therefore, the total of (3 + 3 + 3 + 3) = 12 moves is needed.

**Approach:** The given problem can be solved by using the Greedy Approach which is based on the observations that it is always optimal to start placing the smallest number first at its appropriate position and then place the larger element accordingly. Follow the steps below to solve the problem:

- Initialize a map say
**M**that stores the array elements with their index in the given array**arr[]**. - Traverse the given array
**arr[]**using the variable**i**and update the map**M[arr[i]]**as**M[arr[i]] = (i + 1)**. - Initialize a variable, say
**ans**as**0**that stores the minimum number of total moves required. - Traverse the map
**M**and perform the following steps:- Store the position of the current iterator and the previous iterator in the variables say
**i**and**j**. - Iterate until
**i->second**is less than or equals to**j->second**and increment the value of**ans**by**1**and increment the value of**i->second**by**i->second**.

- Store the position of the current iterator and the previous iterator in the variables say
- After completing the above steps, print the value of
**ans**as the resultant minimum moves.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the minimum number` `// of moves required to sort the numbers` `int` `MinimumMoves(` `int` `arr[], ` `int` `N)` `{` ` ` `// Stores value of number and the` ` ` `// position of the number` ` ` `map<` `int` `, ` `int` `> mp;` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` ` ` `// Update mp[arr[i]]` ` ` `mp[arr[i]] = (i + 1);` ` ` `}` ` ` `// Stores the iterator pointing at` ` ` `// the beginning of the map` ` ` `auto` `it = mp.begin();` ` ` `it++;` ` ` `// Stores the minimum count of moves` ` ` `int` `ans = 0;` ` ` `// Traverse the map mp` ` ` `for` `(` `auto` `i = it; i != mp.end(); i++) {` ` ` ` ` `// Stores previous iterator` ` ` `auto` `j = i;` ` ` `j--;` ` ` `// Iterate while i->second is less` ` ` `// than or equal to j->second` ` ` `while` `(i->second <= j->second) {` ` ` `// Update the i->second` ` ` `i->second += i->second;` ` ` ` ` `// Increment ans by 1` ` ` `ans++;` ` ` `}` ` ` `}` ` ` ` ` `// Return the resultant minimum moves` ` ` `return` `ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `arr[] = { 2, 5, 8, 1, 9 };` ` ` `int` `N = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `cout << MinimumMoves(arr, N);` ` ` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `import` `java.util.*;` `class` `GFG {` ` ` `// Function to find the minimum number` ` ` `// of moves required to sort the numbers` ` ` `static` `int` `MinimumMoves(` `int` `arr[], ` `int` `N)` ` ` `{` ` ` ` ` `// Stores value of number and the` ` ` `// position of the number` ` ` `Map<Integer, Integer> mp` ` ` `= ` `new` `HashMap<Integer, Integer>();` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `// Update mp[arr[i]]` ` ` `if` `(mp.containsKey(arr[i])) {` ` ` `mp.put(arr[i], mp.get(arr[i]) + (i + ` `1` `));` ` ` `}` ` ` `else` `{` ` ` `mp.put(arr[i], (i + ` `1` `));` ` ` `}` ` ` `}` ` ` `// Stores the iterator pointing at` ` ` `// the beginning of the map` ` ` `Iterator<Map.Entry<Integer, Integer> > it` ` ` `= mp.entrySet().iterator();` ` ` `Map.Entry<Integer, Integer> i = it.next();` ` ` ` ` `// Stores the minimum count of moves` ` ` `int` `ans = ` `0` `;` ` ` `// Traverse the map mp` ` ` `while` `(it.hasNext()) {` ` ` `// Stores previous iterator` ` ` `Map.Entry<Integer, Integer> j = i;` ` ` `i = it.next();` ` ` `// Iterate while i->second is less` ` ` `// than or equal to j->second` ` ` `while` `(i.getValue() <= j.getValue()) {` ` ` `// Update the i->second` ` ` `i.setValue(i.getValue() + i.getValue());` ` ` `// Increment ans by 1` ` ` `ans++;` ` ` `}` ` ` `}` ` ` `// Return the resultant minimum moves` ` ` `return` `ans;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `arr[] = { ` `2` `, ` `5` `, ` `8` `, ` `1` `, ` `9` `};` ` ` `int` `N = arr.length;` ` ` `System.out.println(MinimumMoves(arr, N));` ` ` `}` `}` `// This code is contributed by Dharanendra L V.` |

**Output**

12

**Time Complexity:** O(N*log N)**Auxiliary Space:** O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.