Last Updated: 8 Dec, 2020
Sort By Kth Bit
Easy
Asked in companies
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.
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
Approaches
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:
- Create an array/list ‘TEMP_ARR’ of size = ‘N’ for storing all the elements whose ‘K-th’ bit is 1.
- Initialize a variable ‘j’ = 0 to iterate through ‘TEMP_ARR’.
- Initialize a variable ‘p’ = 0 to iterate through ‘ARR’.
- 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.
- If ‘K-th’ bit of arr[i] is 0 then:
- ‘j’ = 0.
- 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.