Sort By Kth Bit

Easy
0/40
Average time to solve is 15m
38 upvotes
Asked in companies
UberAccoliteAjio

Problem statement

You are given an array/list ‘ARR’ of ‘N’ positive integers and an integer ‘K’. Your task is to group all the array elements with ‘K-th’ bit (rightmost bit is ‘1st’ bit) equal to 0 followed by all the elements with ‘K-th’ bit equal to 1.

Note 1: The relative order inside both the groups should remain as it was in the input.

Note 2: You have to return the modified array/list..

For Example : 
If ‘ARR’ is {1,2,3,4} and ‘K’ = 1, then after modification, ‘ARR’ should be {2,4,1,3} because ‘K-th’ (‘K’ = 1) of {2,4} is 0 and ‘K-th’ bit of {1,3} is 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer T representing the number of test cases.

The first line of each test case contains two single space-separated integers ‘N’ and ‘K’ representing size of the input ‘ARR’ and the ‘Kth’ bit as discussed above.

The next line of each test case contains ‘N’ single space-separated integers that represents the elements of the ‘ARR’.
Output Format : 
For each test case, return the modified array as discussed above.
Note: 
You don’t need to print anything, it has already been taken care of. Just implement the given function.
Follow Up: 
Can you do it in linear time?
Constraints: 
1 <= T <= 10
1 <= N <= 10^4
1 <= ARR[i] <= 10^9
1 <= K <= 31

Time Limit: 1 sec
Sample Input 1:
2
4 1
4 3 2 1
5 2
2 5 1 6 7
Sample Output 1:
4 2 3 1
5 1 2 6 7
Explanation For Sample Input 1:
In example 1, the original ‘ARR’ is {4,3,2,1} and ‘K’ = 1. After modification, the ‘ARR’ should be {4,2,3,1} because {4,2} will come first as their 1st bit is 0 and {3,1} will come after that as their 1st bit is 1.

In example 2, the original ‘ARR’ is {2,5,1,6,7} and ‘K’ = 2. After modification the ‘ARR’ should be {5,1,2,6,7} because {5,1} will come first as their 2nd bit is 0 and {2,6,7} will come after that as their 2nd bit is 1.
Sample Input 2:
2
5 1
3 6 2 1 4
5 3
7 6 2 9 3
Sample Output 2:
6 2 4 3 1
2 9 3 7 6
Explanation For Sample Input 2:
In example 1, the original ‘ARR’ is {3,6,2,1,4} and ‘K’ = 1. After modification the ‘ARR’ should be {6,2,4,3,1} because {6,2,4} will come first as their 1st bit is 0 and {3,1} will come after that as their 1st bit is 1.

In example 2, the original ‘ARR’ is {7,6,2,9,3} and ‘K’ = 3. After modification the ‘ARR’ should be {2,9,3,7,6} because {2,9,3} will come first as their 3rd bit is 0 and {7,6} will come after that as their 3rd bit is 1.
Hint

Can you iterate through the ‘ARR’ and check which elements belong to which group?

Approaches (1)
Iteration

The idea is to simply iterate through the ‘ARR’ and check each element whether its ‘K-th’ bit is 0 or 1, and add the element to the respective group.

 

Here is the algorithm:

 

  1. Create an array/list ‘TEMP_ARR’ of size = ‘N’ for storing all the elements whose ‘K-th’ bit is 1.
  2. Initialize a variable ‘j’ = 0 to iterate through ‘TEMP_ARR’.
  3. Initialize a variable ‘p’ = 0 to iterate through ‘ARR’.
  4. Run a loop from 0 to ‘N-1’ (say iterator = ‘i’):
    • If ‘K-th’ bit of arr[i] is 0 then:
      • ‘ARR[p]’ = ‘ARR[i]’. Here, ‘ARR[i]’ is stored in ‘ARR’ at index ‘p’.
      • ‘p’ = ‘p’ + 1.
    • Else:
      • ‘TEMP_ARR[j]’ = ‘ARR[i]’. Here, ‘ARR[i]’ is stored in ‘TEMP_ARR’ at index ‘j’.
      • ‘j’  = ‘j’ + 1.
  5. ‘j’ = 0.
  6. Run a loop from ‘p’ to ‘N-1’ to copy back elements from ‘TEMP_ARR’ to ‘ARR’:
    • ‘ARR[i] = ‘TEMP_ARR[j]’.
    • ‘j’ = ‘j’ + 1.
Time Complexity

O(N), where ‘N’ is the size of ‘ARR’.

 

Because we are iterating through the ‘ARR’ of size ‘N’. Hence the time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the size of ‘ARR’.
 

Because we are making a ‘TEMP_ARR’ of size ‘N’ for storing elements, whose ‘Kth’ bit is equal to 1. Hence, total space complexity is equal to O(N).

Code Solution
(100% EXP penalty)
Sort By Kth Bit
Full screen
Console