# Interview Questions

Ritambhara Technologies - Coding Interview Preparations > Interview Questions > Algorithms > Find numbers with more than k-bits in their binary representations

# Find numbers with more than k-bits in their binary representations

- May 28, 2018
- Posted by: Kamal Rawat
- Category: Algorithms

No Comments

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); }