Given an array of n distinct elements and a number x, arrange array elements according to the absolute difference with x, i. e., the element having a 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 : x = 7, arr[] = {10, 5, 3, 9, 2} Output : arr[] = {5, 9, 10, 3, 2} 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}
Approach: The above problem has been explained in the below post: Sort an array according to absolute difference with given value Sort an array according to absolute difference with a given value “using constant extra space” The above-mentioned solutions have a time complexity of O(nlogn) with an auxiliary space of O(n) and O(n^2) with auxiliary space of O(1) respectively. In this post, a solution with time complexity of O(nlogn) using an auxiliary space of O(1) is proposed. The solution is based on Functors. Compare the absolute value of the difference of the given number, k with the array value arr[i] and returns true if the value of the first object is less than the second object. Using stable_sort order of equivalent values is preserved. Below is the implementation of the above approach:
CPP
// C++ program to sort an array according// absolute difference with x.#include <bits/stdc++.h>using namespace std; // Functor class to perform comparisonclass compare {private: int num; public: compare(int n) { num = n; } // Overloads () operator to perform // the desired comparison int operator()(int arr_num1, int arr_num2) { return abs(num - arr_num1) < abs(num - arr_num2); }}; // Function to sort an array according to// absolute difference with x.void rearrange(int arr[], int n, int k){ // stable_sort sorts all the values in // non-decreasing order and preserves the // order of elements with equal values stable_sort(arr, arr + n, compare(k));} // Function to print the arrayvoid printArray(int arr[], int n){ for (int i = 0; i < n; i++) cout << arr[i] << " ";} // Driver codeint main(){ int arr[] = { 10, 5, 3, 9, 2 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 7; rearrange(arr, n, k); printArray(arr, n); return 0;} |
Java
import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.function.Function;// Functor class to perform comparisonclass Functor implements Function<Integer, Integer> { private int num; public Functor(int num) { this.num = num; } @Override public Integer apply(Integer t) { return Math.abs(num - t); }}class GFG { // Function to sort an array according to // absolute difference with x. static void rearrange(List<Integer> arr, int n, int k) { // stable_sort sorts all the values in // non-decreasing order and preserve the // order of elements with equal values Function<Integer, Integer> compare = new Functor(k); Collections.sort( arr, (a, b) -> compare.apply(a) - compare.apply(b)); } // Function to print the array static void printArray(List<Integer> arr, int n) { for (int num : arr) { System.out.print(num + " "); } } // Driver code public static void main(String[] args) { List<Integer> arr = new ArrayList<>(); arr.add(10); arr.add(5); arr.add(3); arr.add(9); arr.add(2); int n = arr.size(); int k = 7; rearrange(arr, n, k); printArray(arr, n); }} |
Python3
# Python3 program to sort an array according# absolute difference with x.# Functor class to perform comparisonclass functor : def __init__(self, n): self.num = n # this method overloads the () operator def __call__(self, val): return abs(self.num - val) # Function to sort an array according to# absolute difference with x.def rearrange(arr, n, k): # stable_sort sorts all the values in # non-decreasing order and preserves the # order of elements with equal values compare = functor(k) arr.sort(key = lambda x : compare(x) )# Function to print the arraydef printArray(arr, n): print(*arr)# Driver codearr = [10, 5, 3, 9, 2]n = len(arr)k = 7rearrange(arr, n, k);printArray(arr, n); |
C#
// C# program to sort an array according// absolute difference with x.using System;using System.Collections.Generic;// Functor class to perform comparisonpublic class Functor{ private int num; public Functor(int num) { this.num = num; } public static implicit operator Func<int, int>(Functor f) { return (x) => (Math.Abs(f.num - x)); }}class GFG{ // Function to sort an array according to // absolute difference with x. static void rearrange(List<int> arr, int n, int k) { // stable_sort sorts all the values in // non-decreasing order and preserves the // order of elements with equal values Func<int,int> compare = new Functor(k); arr.Sort((a, b) => (compare(a)).CompareTo(compare(b))); } // Function to print the array static void printArray(List<int> arr, int n) { foreach(int num in arr) Console.Write(num + " "); } // Driver code public static void Main(string[] args) { List<int> arr = new List<int> {10, 5, 3, 9, 2}; int n = arr.Count, k = 7; rearrange(arr, n, k); printArray(arr, n); }}// This code s contributed by pasing17. |
Javascript
// JavaScript program to sort an array according// absolute difference with x.// Functor class to perform comparisonclass functor {constructor(n) {this.num = n;}// this method overloads the () operatorcall(val) { return Math.abs(this.num - val);}}// Function to sort an array according to// absolute difference with x.function rearrange(arr, n, k) {// stable_sort sorts all the values in// non-decreasing order and preserve the// order of elements with equal valueslet compare = new functor(k);arr.sort((a, b) => compare.call(a) - compare.call(b));}// Function to print the arrayfunction printArray(arr, n) {console.log(arr);}// Driver codelet arr = [10, 5, 3, 9, 2];let n = arr.length;let k = 7;rearrange(arr, n, k);printArray(arr, n);// This code is contributed by phasing17. |
5 9 10 3 2
Time Complexity : O(n Log n) Auxiliary Space : O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
