Prime Number of Set Bits in Binary Representation

🏠 ⬅️ ➡️

Given two integers left and right, return the count of numbers in the inclusive range [left, right] having a prime number of set bits in their binary representation.

Recall that the number of set bits an integer has is the number of 1's present when written in binary.

  • For example, 21 written in binary is 10101, which has 3 set bits.

Example 1:

Input: left = 6, right = 10 Output: 4 Explanation: 6 -> 110 (2 set bits, 2 is prime) 7 -> 111 (3 set bits, 3 is prime) 8 -> 1000 (1 set bit, 1 is not prime) 9 -> 1001 (2 set bits, 2 is prime) 10 -> 1010 (2 set bits, 2 is prime) 4 numbers have a prime number of set bits.

Example 2:

Input: left = 10, right = 15 Output: 5 Explanation: 10 -> 1010 (2 set bits, 2 is prime) 11 -> 1011 (3 set bits, 3 is prime) 12 -> 1100 (2 set bits, 2 is prime) 13 -> 1101 (3 set bits, 3 is prime) 14 -> 1110 (3 set bits, 3 is prime) 15 -> 1111 (4 set bits, 4 is not prime) 5 numbers have a prime number of set bits.

Constraints:

  • 1 <= left <= right <= 106
  • 0 <= right - left <= 104
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    integer :: left, right, count

    ! Example 1
    left = 6
    right = 10
    count = primeCount(left, right)
    print '(A, I0)', 'Example 1: ', count

    ! Example 2
    left = 10
    right = 15
    count = primeCount(left, right)
    print '(A, I0)', 'Example 2: ', count

contains

    function primeCount(left, right) result(count_)
        implicit none
        integer, intent(in) :: left, right
        integer :: i, j, count_, nsetbits

        count_ = 0
        do i = left, right
            nsetbits = 0
            do j = i, 1, -1
                if (mod(j, 2) == 1) then
                    nsetbits = nsetbits + 1
                end if
            end do
            if (isPrime(nsetbits)) then
                count_ = count_ + 1
            end if
        end do
    end function primeCount

    logical function isPrime(n)
        implicit none
        integer, intent(in) :: n
        integer :: i

        isPrime = .false.
        if (n == 1) then
            isPrime = .true.
        else if (n == 2) then
            isPrime = .true.
        else if (n > 2) then
            do i = 2, int(sqrt(real(n)))
                if (mod(n, i) == 0) then
                    exit
                end if
            end do
            if (i >= sqrt(real(n))) then
                isPrime = .true.
            end if
        end if
    end function isPrime

end program main
✅ Compiled
✅ Executed
❌ Correct 
module prime_set_bits
    implicit none
    private
    public :: prime_set_bits_count

contains

    function prime_set_bits_count(left, right) result(count)
        integer, intent(in) :: left
        integer, intent(in) :: right
        integer :: count
        integer :: i
        integer :: j
        integer :: num_set_bits
        logical :: is_prime

        count = 0
        do i = left, right
            num_set_bits = 0
            do j = i, 1, -1
                if (mod(i, j) == 0) then
                    num_set_bits = num_set_bits + 1
                end if
            end do

            is_prime = .false.
            if (num_set_bits == 2) then
                is_prime = .true.
            else if (num_set_bits == 3) then
                if (i /= 1) then
                    is_prime = .true.
                end if
            else if (num_set_bits == 4) then
                if (i /= 1) then
                    is_prime = .true.
                end if
            end if

            if (is_prime) then
                count = count + 1
            end if
        end do
    end function prime_set_bits_count
end module prime_set_bits

program main
    use prime_set_bits
    implicit none
    integer :: left
    integer :: right
    integer :: count

    left = 6
    right = 10
    count = prime_set_bits_count(left, right)
    write (*,*) "Count of prime set bits in [", left, ", ", right, "] is ", count

    left = 10
    right = 15
    count = prime_set_bits_count(left, right)
    write (*,*) "Count of prime set bits in [", left, ", ", right, "] is ", count
end program main
🌐 Data from online sources 
def is_prime(n: int) -> bool:
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def count_prime_set_bits(left: int, right: int) -> int:
    return sum(is_prime(bin(i).count('1')) for i in range(left, right + 1))

The algorithm first defines a helper function `isPrime` to check if a given number is a prime number. Then, in the main `countPrimeSetBits` function, we iterate through the given range `[left, right]`. For each number, we count the number of 1's in its binary representation and check for primality of that count. If the count is a prime number, we increment the final count of numbers with prime set bits.
🌐 Data from online sources 
#include <bitset>

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}

int countPrimeSetBits(int left, int right) {
    int count = 0;
    for (int i = left; i <= right; ++i)
        count += isPrime(std::bitset<32>(i).count());
    return count;
}

The algorithm first defines a helper function `isPrime` to check if a given number is a prime number. Then, in the main `countPrimeSetBits` function, we iterate through the given range `[left, right]`. For each number, we count the number of 1's in its binary representation and check for primality of that count. If the count is a prime number, we increment the final count of numbers with prime set bits.