Rearrange array elements.

Easy
0/40
Average time to solve is 15m
30 upvotes
Asked in companies
Info Edge India (Naukri.com)Barclays

Problem statement

Given an array ‘A’ having ‘N’ integers and an integer ‘m’. You need to rearrange the array elements such that after re-arrangement difference of array elements with ‘m’ should be in a sorted fashion.

If the difference between any two array elements and ‘m’ is the same, then the element which comes first in the given array will be placed first in the re-arranged array.

For Example 
If we have A =  [3, 5, 7, 9, 2, 6]  and m = 5.
Difference of array elements with m : [2, 0, 2, 4, 3, 1].
Array after rearrangement : [5, 6, 3, 7, 2, 9].
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of each test contains two integers, ‘N’ - number of elements in the array and ‘m’
The second line of each test case contains ‘N’ space-separated integers that make up ‘A’.
Output Format 
For each test case, you need to print space-separated integers denoting the elements of the re-arranged array.

Print the output of each test case in a separated line.
Note 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints 
1 <= T <= 10
1 <= N <= 10^5
1 <= m <= 10^5

Where ‘T’ is the number of test cases, ‘N’ is the length of array ‘A’, and ‘m’ is the value given as described in the problem statement.
Sample Input 1
2
4 6
3 8 1 4
2 12
5 5
Sample Output 1
8 4 3 1
5 5
Explanation Of Sample Input 1
Test Case 1: The array given in this case is [ 3, 8, 1, 4 ] and m = 6.
The difference of array elements with ‘6’ is [ 3, 2, 5, 2 ]. 
Sorted order of difference is 2->2->3->5
Both ‘8’ and ‘2’ have a difference of ‘2’ and ‘8’ comes before ‘6’.So in the rearranged array, ‘8’ will be placed before ‘6’.
Therefore rearranged array will look like 8, 4, 3, 1.

Test Case 2: The difference between the array elements and m, i.e., 12, is the same.
So rearranged array is 5 5.
Sample Input 2
2
5 9
12 4 2 19 5
3 3
1 2 3
Sample Output 2
12 5 4 2 19
3 2 1
Hint

Think of using another array.

Approaches (2)
Brute Force Approach
  • We will solve this problem by finding the array elements that will give the minimum difference between the array element and ‘ m ‘.
  • We will maintain an array ‘visited’ where visited[ i ] = 1 denotes that A[ i ] is visited already.
  • We will iterate through the array ‘A’ and find the array element that is not visited yet or gives minimum difference with ‘ m ‘. Once we get this array element, we will add this to another array ‘result’, mark this element as visited, and iterate through the array again to find the rest of the elements.

 

Algorithm

 

  • Initialize an array ‘visited’ of size ‘N’ and a 1-D array ‘res’ that will store the re-arranged array.
  • Take a variable ‘minVal’ that will store the minimum value obtained in an iteration and a variable  ‘ idx ’ that will store the corresponding element’s index.
  • Run a loop i : 0 to N - 1 to place all the ‘N’ elements in the rearranged array.
    • Store maximum value of int data type in ‘ minVal ’
    • Run a loop j : 0 to N-1
      • If A[ j ] is not visited and difference of A[ j ] with ‘ m ‘ is less than ‘minValue’, update minValue as abs( A[ j ] - m ) and idx = j.
    • Add A[ idx ] to the ‘ res ’ array as A [ idx ]  gives the minimum difference value among the not visited array elements.
  • Return ‘res’.
Time Complexity

O( N^2 ), where ‘ N ’ is the number of elements in the array.

 

For every element in the ‘res’ array, we are iterating through the given array. Therefore time complexity is O( N^2).

Space Complexity

O( N ), where ‘ N ’ is the number of elements in the array.

 

We have used an extra array ‘res’ of size ‘N’, making the space complexity O( N ).

Code Solution
(100% EXP penalty)
Rearrange array elements.
Full screen
Console