Given an array of n distinct elements and a number x, arrange array elements according to the absolute difference with x, i. e., element having minimum difference comes first and so on.

Note : If two or more elements are at equal distance arrange them in same sequence as in the given array.

Examples :

Input :arr[] : x = 7, arr[] = {10, 5, 3, 9, 2}Output :arr[] = {5, 9, 10, 3, 2}Explanation:7 - 10 = 3(abs) 7 - 5 = 2 7 - 3 = 4 7 - 9 = 2(abs) 7 - 2 = 5 So according to the difference with X, elements are arranged as 5, 9, 10, 3, 2.Input :x = 6, arr[] = {1, 2, 3, 4, 5}Output :arr[] = {5, 4, 3, 2, 1}Input :x = 5, arr[] = {2, 6, 8, 3}Output :arr[] = {6, 3, 2, 8}

The idea is to use a self balancing binary search tree. We traverse input array and for every element, we find its difference with x and store the difference as key and element as value in self balancing binary search tree. Finally we traverse the tree and print its inorder traversal which is required output.

**C++ Implementation : **

In C++, self-balancing-bianry-search-tree is implemented by set, map and multimap. We can’t use set here as we have key value pairs (not only keys). We also can’t directly use map also as a single key can belong to multiple values and map allows a single value for a key. So we use multimap which stores key value pairs and can have multiple values for a key.

- Store the values in the multimap with the difference with X as key.
- In multiimap, the values will be already in sorted order according to key i.e. difference with X because it implements self-balancing-bianry-search-tree internally.
- Update all the values of array with the values of map so that array has the required output.

`// C++ program to sort an array according absolute ` `// difference with x. ` `#include<bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// Function to sort an array according absolute ` `// difference with x. ` `void` `rearrange(` `int` `arr[], ` `int` `n, ` `int` `x) ` `{ ` ` ` `multimap<` `int` `, ` `int` `> m; ` ` ` `multimap<` `int` `,` `int` `>:: iterator it; ` ` ` `// Store values in a map with the difference ` ` ` `// with X as key ` ` ` `for` `(` `int` `i = 0 ; i < n; i++) ` ` ` `m.insert(make_pair(` `abs` `(x-arr[i]),arr[i])); ` ` ` ` ` `// Update the values of array ` ` ` `int` `i = 0; ` ` ` `for` `(it = m.begin(); it != m.end(); it++) ` ` ` `arr[i++] = (*it).second ; ` `} ` ` ` `// Function to print the array ` `void` `printArray(` `int` `arr[] , ` `int` `n) ` `{ ` ` ` `for` `(` `int` `i = 0 ; i < n; i++) ` ` ` `cout << arr[i] << ` `" "` `; ` `} ` ` ` `// Driver code ` `int` `main() ` `{ ` ` ` `int` `arr[] = {10, 5, 3, 9 ,2}; ` ` ` `int` `n = ` `sizeof` `(arr)/` `sizeof` `(arr[0]); ` ` ` `int` `x = 7; ` ` ` `rearrange(arr, n, x); ` ` ` `printArray(arr, n); ` ` ` `return` `0; ` `} ` |

Output:

5 9 10 3 2

Time Complexity : O(n Log n)

Auxiliary Space : O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments