404. Find all the numbers in the range which has prime set bits.

Objective: Given a range, find all the numbers in the range which has prime set bits.

Example:

L = 4, R = 10
Output: 5
Explanation:
4 = 1 0 0 ( not prime)
5 = 1 0 1 (prime)
6 = 1 1 0 (prime)
7 = 1 1 1 (prime)
8 = 1 0 0 0 ( not prime)
9 = 1 0 0 1 (prime)
10 = 1 1 0 0 (prime)
Total 5 numbers which has prime set bits.

Approach:

1. Iterate through all numbers from L to R
   1. For each number, count no of set bits.
   2. check if the count is a prime number, if yes add it to result.

Time Complexity: O( N Sqrt (N) )

This algorithm can be improved using Sieve of Eratosthenes Algorithm. We will implement that in our next article -  Numbers with prime set bits in a given range using Sieve of Eratosthenes Algorithm

Output:

5

Related Problems:

- Print All Possible Subsets with Sum equal to a given Number Hard
- Check if Number is divisible by its digits Beginner
- Convert Roman Number to Integer Beginner
- Convert Integer to Roman Medium
- Check if given number is Prime - O(√N) Solution Medium