0

Sort by Kth bit

Difficulty: EASY
Avg. time to solve
15 min
Success Rate
90%

Problem Statement
Suggest Edit

Divide the given array into two parts based on the Kth bit (rightmost bit is 1st bit) of each element. All the elements with Kth bit 0 should come first. Order does not matter. Do it in linear time and constant space.

Input format :
The first line contains a single integer T representing the number of test cases.
Each test case consists of:-
Line 1: Integer N 
Line 2: N integers separated by a space.
Line 3: Integer K
Output format :
For each test case, just make the changes in the array.

Constraints:

1 <= T <= 10
1 <= N <= 10000
1 <= K <= 31

Time Limit: 1 sec
Sample Input :
1
4
1 2 3 4
1
Sample Output :
2 4 3 1 
Want to solve this problem? Login now to get access to solve the problems