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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Add two numbers in Scala - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Goal Parser Interpretation LeetCode Solution - The Coding Shala

Maximum Population Year LeetCode Solution - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala