Arranging Array

Easy

0/40

Average time to solve is 15m

Contributed by

82 upvotes

Asked in companies

Problem statement

You are given an array of N integers. Your task is to rearrange the elements of the array such that the total XOR sum of all adjacent elements is maximized.

The XOR sum is defined as follows. For an array a of size N, compute:

F = (a[1] ⊕ a[0]) + (a[2] ⊕ a[1]) + ... + (a[N-1] ⊕ a[N-2]) where ⊕ denotes the bitwise XOR operator.

Your goal is to output a permutation of the original array that results in the maximum possible value of F.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains T, the number of test cases. 

For each test case, the first line contains a number ‘N’, which is the size of the array.
The next line contains N space-separated integers, that denote the values of the elements in the array.

Output Format :

The output of each test case contains ‘N’ integers, denoting the order in which the elements should be kept such that the result is largest.

Constraints :

1 <= T <= 5
1 <= N <= 3000
1 <= data <= 10^5

where ‘T’ is the number of test cases, N is the number of elements in the array. 

Time Limit : 1sec

Sample Input 1 :

1
3
5 4 6

Sample Output 1 :

6 5 4

Explanation of Sample Input 1 :

This is because ( 4 ^ (5 ^ 6) ) is the greatest value when compared to any other permutations.

Sample Input 2 :

1
2
2 3

Sample Output 2 :

2 3

Hint 1

Does sorting the elements help?

Approaches (1)

Approach 1

Sorting

To maximize the sum of XOR values between adjacent elements, we observe the following:

Placing the number 1 adjacent to any other number typically reduces the XOR value, because 1 ^ x tends to be smaller compared to other combinations.
Therefore, it's beneficial to:
- Place all occurrences of 1 at the beginning.
- Arrange the remaining elements in descending order, as larger differences between adjacent values tend to yield higher XOR values.

Algorithm:

Sort the array in descending order.
Print all the ones, if present.
From the remaining array print it in descending order making sure not to reprint the ones again.

Time Complexity

O(N * log(N)), where N is the number of elements in the array.

Since we are sorting the array and then traversing the array to get the final output, the net time complexity will be O(N * log(N)) + O(N) = O(N * log(N)).

Space Complexity

O(1)

Since we did not use any extra space.

(100% EXP penalty)

Arranging Array

Console