### Prime Number of Set Bits in Binary Representation LeetCode Solution - The Coding Shala

Home >> LeetCode >> Prime Number of Set Bits in Binary Representation

In this post, we will learn how to solve LeetCode's Prime Number of Set Bits in Binary Representation Problem and will implement its solution in Java.

## Prime Number of Set Bits in Binary Representation Problem

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

Example 1:
Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)

Practice this problem on LeetCode.

## LeetCode - Prime Number of Set Bits in Binary Representation Java Solution

#### Approach 1

First count set bits in number then check if it's prime or not.

Java Program:

```class Solution {

public boolean isPrime(int num) {
if(num < 2) return false;
for(int i = 2; i*i <= num; i++) {
if(num%i == 0) return false;
}
return true;
}

public int countPrimeSetBits(int L, int R) {
int res = 0;
for(int i=L; i<=R; i++) {
int setBits = Integer.bitCount(i);
if(isPrime(setBits)) res++;
}
return res;
}
}
```

Other Posts You May Like