Sort By Kth Bit
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

Question

Sort By Kth Bit

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

Accepted Answer

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:

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.
‘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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(n)Explanation:

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).

Python (3.5)

'''
    
    Time Complexity : O(N)
    Space Complexity : O(N)

    Where N is the number of elements in the array.

'''

def sortArrayByKBit(n, k, arr):

    j = 0
    p = 0

    temparr = [0]*n
    # Loop to through arr.
    for i in range(n):
        # If Kth bit of current element is 0.
        if((arr[i] & (1 << (k-1))) == 0):
            arr[p] = arr[i]
            p += 1
        # If Kth bit of current element is 1.
        else:
            temparr[j] = arr[i]
            j += 1

    j = 0
    # Copy elements from temparr back to arr.
    for i in range(p,n):
        arr[i] = temparr[j]
        j += 1

    # Return modified array.
    return arr

Java (SE 1.8)

/*

    Time Complexity : O(N)
    Space Complexity : O(N)

    Where N is the number of elements in the array.
   

*/


public class Solution {
	public static int[] sortArrayByKBit(int n, int k, int arr[]) {
	    
        int j = 0;
        int p = 0;
    
        int temparr[] = new int[n];
    
        // Loop to through arr.
        for (int i = 0; i < n; i++) {
            // If Kth bit of current element is 0.
            if ((arr[i] & (1 << (k - 1))) == 0) {
                arr[p++] = arr[i];
            }
            // If Kth bit of current element is 1.
            else {
                temparr[j++] = arr[i];
            }
        }
    
        j = 0;
        // Copy elements from temparr back to arr.
        for (int i = p; i < n; i++) {
            arr[i] = temparr[j++];
        }
        // Return modified array.
        return arr;
	}
}

C++ (g++ 5.4)

/*

    Time Complexity : O(N)
    Space Complexity : O(N)

    Where N is the number of elements in the array.

    
*/

vector < int > sortArrayByKBit(int n, int k, vector < int > & arr) {
    int j = 0;
    int p = 0;

    vector < int > temparr(n);

    // Loop to through arr.
    for (int i = 0; i < n; i++) {
        // If Kth bit of current element is 0.
        if ((arr[i] >> (k - 1)) % 2 == 0) {
            arr[p++] = arr[i];
        }
        // If Kth bit of current element is 1.
        else {
            temparr[j++] = arr[i];
        }
    }

    j = 0;
    // Copy elements from temparr back to arr.
    for (int i = p; i < n; i++) {
        arr[i] = temparr[j++];
    }
    // Return modified array.
    return arr;
}