## Sunday, April 17, 2016

### Convert an array to reduced form - GeeksforGeeks

Convert an array to reduced form - GeeksforGeeks
Given an array with n distinct elements, convert the given array to a form where all elements are in range from 0 to n-1. The order of elements is same, i.e., 0 is placed in place of smallest element, 1 is placed for second smallest element, … n-1 is placed for largest element.
`Input:  arr[] = {10, 40, 20}  Output: arr[] = {0, 2, 1}    `
`Input:  arr[] = {5, 10, 40, 30, 20}  Output: arr[] = {0, 1, 4, 3, 2}  `
Expected time complexity is O(n Log n).

`void` `convert(``int` `arr[], ``int` `n)`
`{`
`    ``// Create a temp array and copy contents`
`    ``// of arr[] to temp`
`    ``int` `temp[n];`
`    ``memcpy``(temp, arr, n*``sizeof``(``int``));`

`    ``// Sort temp array`
`    ``sort(temp, temp + n);`

`    ``// Create a hash table. Refer `
`    ``// http://tinyurl.com/zp5wgef `
`    ``unordered_map<``int``, ``int``> umap;`

`    ``// One by one insert elements of sorted`
`    ``// temp[] and assign them values from 0`
`    ``// to n-1`
`    ``int` `val = 0;`
`    ``for` `(``int` `i = 0; i < n; i++)`
`        ``umap[temp[i]] = val++;`

`    ``// Convert array by taking positions from`
`    ``// umap`
`    ``for` `(``int` `i = 0; i < n; i++)`
`        ``arr[i] = umap[arr[i]];`
`}`