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

Shell Script to Create a Simple Calculator - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Java Program to Convert Binary to Decimal - The Coding Shala

LeetCode - Shuffle the Array Solution - The Coding Shala

Introduction to Kotlin Programming Language for Backend Development - The Coding Shala