Given an array of unsigned integers, print all the numbers that have more than k bits set in their binary representation. For example, if k = 2, and input array is:
int arr[] = {2, 1, 15, 9, 7, 14, 32, 127};
Then the output should be:
15 7 14 127
Because all of these numbers has more than 2 bits set in their binary representations:
Solution:
The brute-force solution is to use mask and check whether a bit in a number is set of not for each bit in the number. In this case, we have to check for sizeof(int) bits.
A better solution is to use the logic used in this post, where we saw how to reset the last set-bit of a number in constant time:
This is a constant-time improvement, where the loop is executed only for set-bits.
// COUNT THE NUMBER OF SET BITS IN num int bitSetCount(int num) { int cnt = 0; while(num >0) { num = num & (num-1); cnt++; } return cnt; } // PRINT NUMBERS WITH MORE THAN k BITS SET IN THEIR BINARY REPRESENTATION void printNumbersForSetBits(int *arr, int n, int k) { // FOR EACH NUMBER for(int i=0; ik) cout<<arr[i]<<" "; } } int main() { int arr[] = {2, 1, 15, 9, 7, 14, 32, 127}; printNumbersForSetBits(arr, 8, 2); }