Sorting array elements with set bits equal to K
Given an array of integers and a number . The task is to sort only those elements of the array whose total set bits are equal to K. Sorting must be done at their relative positions only without affecting any other elements.
Examples:
Input : arr[] = {32, 1, 9, 4, 64, 2}, K = 1 Output : 1 2 9 4 32 64 All of the elements except 9 has exactly 1 bit set. So, all elements except 9 are sorted without affecting the position of 9 in the input array. Input : arr[] = {2, 15, 12, 1, 3, 9}, K = 2 Output : 2 15 3 1 9 12
Approach:
- Initialise two empty vectors.
- Traverse the array, from left to right and check the set bits of each element.
- Here, C++ inbuilt function __builtin_popcount() to count setbits.
- In first vector, insert the index of all elements with set bits equal to K.
- In second vector, insert the elements with set bits equal to K.
- Sort the second vector.
- Now, we have the index of all elements with set bit equals to K in sorted order and also all of the elements with set bit as K in sorted order.
- So, insert the elements of the second vector into the array at the indices present in first vector one by one.
Below is the implementation of the above approach:
C++
// C++ program for sorting array elements // with set bits equal to K #include <bits/stdc++.h> using namespace std; // Function to sort elements with // set bits equal to k void sortWithSetbits( int arr[], int n, int k) { // initialise two vectors vector< int > v1, v2; for ( int i = 0; i < n; i++) { if (__builtin_popcount(arr[i]) == k) { // first vector contains indices of // required element v1.push_back(i); // second vector contains // required elements v2.push_back(arr[i]); } } // sorting the elements in second vector sort(v2.begin(), v2.end()); // replacing the elements with k set bits // with the sorted elements for ( int i = 0; i < v1.size(); i++) arr[v1[i]] = v2[i]; // printing the new sorted array elements for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // Driver code int main() { int arr[] = { 14, 255, 1, 7, 13 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 3; sortWithSetbits(arr, n, k); return 0; } |
Java
// Java program for sorting array elements // with set bits equal to K import java.util.*; // Represents node of a doubly linked list class Node { // Function to sort elements with // set bits equal to k static void sortWithSetbits( int arr[], int n, int k) { // initialise two vectors Vector<Integer> v1 = new Vector<>(), v2 = new Vector<>(); for ( int i = 0 ; i < n; i++) { if (Integer.bitCount(arr[i]) == k) { // first vector contains indices of // required element v1.add(i); // second vector contains // required elements v2.add(arr[i]); } } // sorting the elements in second vector Collections.sort(v2); // replacing the elements with k set bits // with the sorted elements for ( int i = 0 ; i < v1.size(); i++) { arr[v1.get(i)] = v2.get(i); } // printing the new sorted array elements for ( int i = 0 ; i < n; i++) { System.out.print(arr[i] + " " ); } } // Driver code public static void main(String[] args) { int arr[] = { 14 , 255 , 1 , 7 , 13 }; int n = arr.length; int k = 3 ; sortWithSetbits(arr, n, k); } } // This code is contributed by Princi Singh |
Python3
# Python 3 program for sorting array # elements with set bits equal to K # Function to sort elements with # set bits equal to k def sortWithSetbits(arr, n, k): # initialise two vectors v1 = [] v2 = [] for i in range ( 0 , n, 1 ): if ( bin (arr[i]).count( '1' ) = = k): # first vector contains indices # of required element v1.append(i) # second vector contains # required elements v2.append(arr[i]) # sorting the elements in second vector v2.sort(reverse = False ) # replacing the elements with k set # bits with the sorted elements for i in range ( 0 , len (v1), 1 ): arr[v1[i]] = v2[i] # printing the new sorted array elements for i in range ( 0 , n, 1 ): print (arr[i], end = " " ) # Driver code if __name__ = = '__main__' : arr = [ 14 , 255 , 1 , 7 , 13 ] n = len (arr) k = 3 sortWithSetbits(arr, n, k) # This code is contributed by # Surendra_Gangwar |
C#
// C# program for sorting array elements // with set bits equal to K using System; using System.Collections.Generic; // Represents node of a doubly linked list public class Node { // Function to sort elements with // set bits equal to k static void sortWithSetbits( int []arr, int n, int k) { // initialise two vectors List< int > v1 = new List< int >(); List< int > v2 = new List< int >(); for ( int i = 0; i < n; i++) { if (bitCount(arr[i]) == k) { // first vector contains indices of // required element v1.Add(i); // second vector contains // required elements v2.Add(arr[i]); } } // sorting the elements in second vector v2.Sort(); // replacing the elements with k set bits // with the sorted elements for ( int i = 0; i < v1.Count; i++) { arr[v1[i]] = v2[i]; } // printing the new sorted array elements for ( int i = 0; i < n; i++) { Console.Write(arr[i] + " " ); } } static int bitCount( long x) { int setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits; } // Driver code public static void Main(String[] args) { int []arr = {14, 255, 1, 7, 13}; int n = arr.Length; int k = 3; sortWithSetbits(arr, n, k); } } /* This code is contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript program for sorting array elements // with set bits equal to K function bitCount(x) { var setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits; } // Function to sort elements with // set bits equal to k function sortWithSetbits(arr, n, k) { // initialise two vectors var v1 = [], v2 = []; for ( var i = 0; i < n; i++) { if (bitCount(arr[i]) == k) { // first vector contains indices of // required element v1.push(i); // second vector contains // required elements v2.push(arr[i]); } } // sorting the elements in second vector v2.sort((a,b)=> a-b); // replacing the elements with k set bits // with the sorted elements for ( var i = 0; i < v1.length; i++) arr[v1[i]] = v2[i]; // printing the new sorted array elements for ( var i = 0; i < n; i++) document.write( arr[i] + " " ); } // Driver code var arr = [14, 255, 1, 7, 13 ]; var n = arr.length; var k = 3; sortWithSetbits(arr, n, k); </script> |
Output:
7 255 1 13 14
Time Complexity: O(n*log(n))
Auxiliary Space: O(n)
Contact Us