Skip to main content
CodePeet

Prime Number of Set Bits in Binary Representation

Try it yourself
EasyProblemExternal link

Description

You are given two integers left and right. Count how many numbers from left to right, both included, have a prime number of set bits.

  • The set bits of a number are the 1s in its binary form. For example, 26 is 11010 in binary (16 + 8 + 2), so it has 3 set bits.
  • A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, … The number 1 is not prime.

Examples

Example 1

Input: left = 18, right = 24

Output: 6

Explanation:

  • 18 = 10010 → 2 set bits, prime ✓
  • 19 = 10011 → 3 set bits, prime ✓
  • 20 = 10100 → 2 set bits, prime ✓
  • 21 = 10101 → 3 set bits, prime ✓
  • 22 = 10110 → 3 set bits, prime ✓
  • 23 = 10111 → 4 set bits, not prime (4 = 2 × 2)
  • 24 = 11000 → 2 set bits, prime ✓

Six of the seven numbers count.

Example 2

Input: left = 1, right = 5

Output: 2

Explanation:

  • 1 = 1 → 1 set bit. 1 is not prime.
  • 2 = 10 → 1 set bit, not prime.
  • 3 = 11 → 2 set bits, prime ✓
  • 4 = 100 → 1 set bit, not prime.
  • 5 = 101 → 2 set bits, prime ✓

Every power of two has exactly one set bit, so powers of two never count.

Example 3

Input: left = 15, right = 16

Output: 0

Explanation: 15 = 1111 has 4 set bits, and 4 is not prime. 16 = 10000 has 1 set bit, and 1 is not prime. Neither counts.

Constraints

  • 1 ≤ left ≤ right ≤ 10^6
  • 0 ≤ right − left ≤ 10^4

Editorial

Brute Force

Intuition

Do exactly what the question says, one number at a time: count its set bits, then check whether that count is prime.

Counting set bits. In binary, each position stands for a power of two: 1, 2, 4, 8, 16, … read from the right. 18 is 10010 because 18 = 16 + 2. To count the 1s, look at the rightmost bit (x & 1, which is the same as x % 2), add it to a tally, then drop that bit by shifting right (x >> 1, the same as dividing by 2 and dropping the remainder). Repeat until x is 0. Each shift removes one bit, so this takes one round per bit.

Checking for a prime. A count k is prime when it is at least 2 and no number from 2 upward divides it. You only need to try divisors d with d × d ≤ k. If k had a divisor larger than that, it would pair with one smaller than that, which you would already have tried.

Step-by-Step Explanation

We trace Example 1, left = 18 and right = 24. The first number, 18, is counted bit by bit; after that each number is shown with its set bits highlighted: green when the count is prime, amber when it is not.

Step 1: Start with x = 18, which is 10010 in binary (16 + 2). The tally of set bits is 0.

Step 2: The bit worth 1 is 0 — nothing to add.

Step 3: The bit worth 2 is 1 — the tally becomes 1.

Step 4: The bit worth 4 is 0 — nothing to add.

Step 5: The bit worth 8 is 0 — nothing to add.

Step 6: The bit worth 16 is 1 — the tally becomes 2. x is now 0, so the counting stops.

Step 7: 18 has 2 set bits. Trial division finds no divisor of 2 (no d ≥ 2 has d × d ≤ 2), so 2 is prime. The count is now 1.

Step 8: x = 19 = 10011: 3 set bits, prime — count 2.

Step 9: x = 20 = 10100: 2 set bits, prime — count 3.

Step 10: x = 21 = 10101: 3 set bits, prime — count 4.

Step 11: x = 22 = 10110: 3 set bits, prime — count 5.

Step 12: x = 23 = 10111: 4 set bits, not prime — count stays 5.

Step 13: x = 24 = 11000: 2 set bits, prime — count 6.

Step 14: All seven numbers are checked; only 23 missed. Return 6.

Brute Force — Counting Bits One at a Time — The bits of each number, with their place values underneath: 18 is counted bit by bit, then each later number is counted and its tally tested for being prime.

Algorithm

  1. Set count = 0.
  2. For each x from left to right:
    • Count the bits: bits = 0; while x > 0, add x & 1 to bits and shift x right by one.
    • Test the count: it is prime if it is at least 2 and no d with d × d ≤ bits divides it.
    • If it is prime, add 1 to count.
  3. Return count.

Code

class Solution {
    int setBits(int x) {
        int bits = 0;
        while (x > 0) {
            bits += x & 1;  // the lowest bit is 1 or 0
            x >>= 1;        // drop it and look at the next one
        }
        return bits;
    }

    bool isPrime(int k) {
        if (k < 2) return false;
        for (int d = 2; d * d <= k; d++)
            if (k % d == 0) return false;
        return true;
    }

public:
    int countPrimeSetBits(int left, int right) {
        int count = 0;
        for (int x = left; x <= right; x++)
            if (isPrime(setBits(x))) count++;
        return count;
    }
};
class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        count = 0
        for x in range(left, right + 1):
            if self.is_prime(self.set_bits(x)):
                count += 1
        return count

    def set_bits(self, x: int) -> int:
        bits = 0
        while x > 0:
            bits += x & 1  # the lowest bit is 1 or 0
            x >>= 1        # drop it and look at the next one
        return bits

    def is_prime(self, k: int) -> bool:
        if k < 2:
            return False
        d = 2
        while d * d <= k:
            if k % d == 0:
                return False
            d += 1
        return True
class Solution {
    public int countPrimeSetBits(int left, int right) {
        int count = 0;
        for (int x = left; x <= right; x++)
            if (isPrime(setBits(x))) count++;
        return count;
    }

    private int setBits(int x) {
        int bits = 0;
        while (x > 0) {
            bits += x & 1;  // the lowest bit is 1 or 0
            x >>= 1;        // drop it and look at the next one
        }
        return bits;
    }

    private boolean isPrime(int k) {
        if (k < 2) return false;
        for (int d = 2; d * d <= k; d++)
            if (k % d == 0) return false;
        return true;
    }
}

Complexity Analysis

Let n = right − left + 1 be the number of values checked.

Time Complexity: O(n · log right). Each number has about log₂(right) + 1 bits, at most 20 here, and the loop takes one round per bit. The prime test on a count of at most 20 tries at most 3 divisors.

Space Complexity: O(1). A few integer variables.

Why This Approach Is Not Efficient

For these limits this is already fast: at most 10,001 numbers × 20 bits is about 200,000 small steps. But it repeats two kinds of work.

  • Bits are counted one at a time. Every language used here has a built-in that returns the number of set bits directly, and on modern processors it is a single machine instruction.
  • The same prime question is asked over and over. A number below 10^6 has at most 20 set bits, so there are only 21 possible counts (0 to 20). Yet the prime test runs again for every single number. The answer for each possible count can be worked out once and looked up afterwards.

Measured on the whole range 1 to 10^6, a million numbers, this approach takes about 0.49 s in Python. The next one takes about 0.04 s.

Better Approach - Built-In Bit Count and a Prime Mask

Intuition

Fix both repeats.

Count the bits with the built-in. x.bit_count() in Python, __builtin_popcount(x) in C++ and Integer.bitCount(x) in Java all return the number of set bits in one call.

Look up "is this count prime?" in a mask. Because right ≤ 10^6 < 2^20, no number here has more than 20 set bits. The primes up to 20 are 2, 3, 5, 7, 11, 13, 17 and 19. Build one integer whose bit p is 1 exactly when p is one of those primes:

bit position:  19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
mask:           1  0  1  0  0  0  1  0  1  0  0  0  1  0  1  0  1  1  0  0

That integer is 0b10100010100010101100 = 665772. To ask whether a count k is prime, shift the mask right by k and look at the last bit: (mask >> k) & 1 is 1 for a prime and 0 otherwise. One shift and one AND replace the whole trial-division loop.

Step-by-Step Explanation

We trace Example 1 again, left = 18 and right = 24. The row shows the numbers; the row underneath fills in each one's set-bit count as it is read.

Step 1: Build the mask once: its bits at positions 2, 3, 5, 7, 11, 13, 17 and 19 are 1.

Step 2: 18: the built-in count is 2; bit 2 of the mask is 1, so the count becomes 1.

Step 3: 19: the built-in count is 3; bit 3 of the mask is 1, so the count becomes 2.

Step 4: 20: the built-in count is 2; bit 2 of the mask is 1, so the count becomes 3.

Step 5: 21: the built-in count is 3; bit 3 of the mask is 1, so the count becomes 4.

Step 6: 22: the built-in count is 3; bit 3 of the mask is 1, so the count becomes 5.

Step 7: 23: the built-in count is 4; bit 4 of the mask is 0. No change.

Step 8: 24: the built-in count is 2; bit 2 of the mask is 1, so the count becomes 6.

Step 9: Return 6 — one built-in count and one mask lookup per number.

Built-In Bit Count and a Prime Mask — Each number gets its set-bit count from one built-in call (the row underneath), and one look at the prime mask says whether that count is prime.

Algorithm

  1. Set mask = 665772 (bits 2, 3, 5, 7, 11, 13, 17 and 19 are 1) and count = 0.
  2. For each x from left to right:
    • k = the built-in set-bit count of x.
    • Add (mask >> k) & 1 to count.
  3. Return count.

Code

class Solution {
public:
    int countPrimeSetBits(int left, int right) {
        // right <= 10^6 < 2^20, so no number has more than 20 set bits. The primes up to 20 are
        // 2, 3, 5, 7, 11, 13, 17 and 19; bit p of this mask is 1 exactly when p is one of them.
        const int primeMask = 0b10100010100010101100;  // 665772
        int count = 0;
        for (int x = left; x <= right; x++)
            count += (primeMask >> __builtin_popcount(x)) & 1;
        return count;
    }
};
class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        # right <= 10^6 < 2^20, so no number has more than 20 set bits. The primes up to 20 are
        # 2, 3, 5, 7, 11, 13, 17 and 19; bit p of this mask is 1 exactly when p is one of them.
        prime_mask = 0b10100010100010101100  # 665772
        count = 0
        for x in range(left, right + 1):
            count += (prime_mask >> x.bit_count()) & 1
        return count
class Solution {
    public int countPrimeSetBits(int left, int right) {
        // right <= 10^6 < 2^20, so no number has more than 20 set bits. The primes up to 20 are
        // 2, 3, 5, 7, 11, 13, 17 and 19; bit p of this mask is 1 exactly when p is one of them.
        final int primeMask = 0b10100010100010101100;  // 665772
        int count = 0;
        for (int x = left; x <= right; x++)
            count += (primeMask >> Integer.bitCount(x)) & 1;
        return count;
    }
}

Complexity Analysis

Let n = right − left + 1.

Time Complexity: O(n). Each number costs one built-in count and one shift, both constant time.

Space Complexity: O(1). One mask and a counter.

Why This Approach Is Not Efficient

This is as fast as a method can be if it looks at every number, and that is the remaining cost. The work grows with the length of the range. Here the range holds at most 10,001 numbers, so it finishes instantly. If the question allowed left = 1 and right = 10^9, it would have to visit a billion numbers. At the rate measured above, about 0.04 s per million numbers in Python, that is around 40 seconds. It is doing that to produce a single number.

A count does not need every item to be looked at one by one. The numbers up to 24 that start 0xxxx in binary are simply every 4-bit pattern. How many of those patterns have exactly 2 ones is a counting question with a formula answer, and no pattern has to be visited to answer it. The next approach counts whole blocks of numbers at once like that.

Optimal Approach - Count Whole Blocks by Binary Digits

Intuition

Step 1: turn the range into two counts that start from 0. Let count_up_to(n) be how many numbers from 0 to n have a prime number of set bits. The numbers from left to right are the numbers up to right minus the numbers up to left − 1:

answer = count_up_to(right) − count_up_to(left − 1)

Step 2: split the numbers up to n into blocks, using the bits of n. Take n = 24 = 11000. Every smaller number, written with the same 5 bits, agrees with 24 for a while and then, at the first place they differ, has a 0 where 24 has a 1. After that place it can be anything and still stay smaller. So the numbers up to 24 fall into one block for each 1 in 24, plus 24 itself:

  • 0xxxx: the numbers 0 to 15, where the four x bits are free.
  • 10xxx: the numbers 16 to 23, where the three x bits are free.
  • 11000: 24 itself.

A 0 in 24 opens no block, because a smaller number cannot put anything below 0 there.

The numbers from 0 to 24 split into three blocks by the bits of 24 = 11000: the block 0xxxx (0 to 15) with four free bits holds 6 + 4 = 10 numbers with a prime count of set bits, the block 10xxx (16 to 23) with three free bits and one 1 fixed holds 3 + 3 = 6, and 24 itself, with two set bits, adds 1: 10 + 6 + 1 = 17.

Step 3: count each block with a formula. Inside a block, the fixed part already holds some number of ones, and the i free bits can form any pattern. The number of i-bit patterns with exactly j ones is C(i, j), "i choose j": the number of ways to pick which j of the i bits are the 1s. The block contributes C(i, p − ones) for every prime p that the free bits can reach.

For 10xxx, one 1 is fixed and 3 bits are free. The total can be 2 (one more 1: C(3, 1) = 3 ways) or 3 (two more: C(3, 2) = 3 ways), so the block holds 6 numbers with a prime count. You can check this by hand: 17, 18, 19, 20, 21, 22.

Getting C(i, j) without multiplying big numbers. Build Pascal's triangle. Look at the first free bit: it is either a 1, leaving j − 1 ones for the other i − 1 bits, or a 0, leaving all j. So C(i, j) = C(i − 1, j − 1) + C(i − 1, j), starting from C(i, 0) = 1. With at most 20 bits, the whole table is 21 × 21 small numbers.

Step-by-Step Explanation

We trace Example 1: the answer for 18 to 24 is count_up_to(24) − count_up_to(17). The cells are the bits of n with their place values underneath; the row below records what each bit added.

Step 1: Count up to 24 = 11000: start with total 0 and no ones fixed yet.

Step 2: The bit worth 16 is 1: the block 0xxxx (0–15) has 4 free bits and 0 ones fixed, giving 6 + 4 = 10. The total is 10.

Step 3: The bit worth 8 is 1: the block 10xxx (16–23) has 3 free bits and 1 one fixed, giving 3 + 3 = 6. The total is 16.

Step 4: The bit worth 4 is 0: no block, nothing to add.

Step 5: The bit worth 2 is 0: no block, nothing to add.

Step 6: The bit worth 1 is 0: no block, nothing to add.

Step 7: 24 itself has 2 set bits — prime, add 1. count_up_to(24) = 17.

Step 8: Count up to 17 = 10001: start with total 0 and no ones fixed yet.

Step 9: The bit worth 16 is 1: the block 0xxxx (0–15) has 4 free bits and 0 ones fixed, giving 6 + 4 = 10. The total is 10.

Step 10: The bit worth 8 is 0: no block, nothing to add.

Step 11: The bit worth 4 is 0: no block, nothing to add.

Step 12: The bit worth 2 is 0: no block, nothing to add.

Step 13: The bit worth 1 is 1: the block 10000 (just 16) has 0 free bits and 1 one fixed, and no prime total is possible — 0. The total is 10.

Step 14: 17 itself has 2 set bits — prime, add 1. count_up_to(17) = 11.

Step 15: The answer is count_up_to(24) − count_up_to(17) = 17 − 11 = 6.

Counting by Binary Digits — Up to 24, Then Up to 17 — The bits of n with their place values; at every 1, a whole block of smaller numbers is counted with C(free bits, ones needed), and the row underneath collects what each bit added.

Algorithm

count_up_to(n):

  1. If n < 0, return 0.
  2. Let width be the number of bits in n. Build Pascal's triangle ways[a][b] for a, b ≤ width: ways[a][0] = 1 and ways[a][b] = ways[a−1][b−1] + ways[a−1][b].
  3. Set total = 0 and ones = 0. For each bit position i from width − 1 down to 0:
    • If bit i of n is 1:
      • For each prime p in 2, 3, 5, 7, 11, 13, 17, 19 with 0 ≤ p − ones ≤ i, add ways[i][p − ones] to total.
      • Add 1 to ones.
  4. If ones is prime, add 1 to total. This counts n itself.
  5. Return total.

Answer: count_up_to(right) − count_up_to(left − 1).

Code

#include <vector>
using namespace std;

class Solution {
    // How many x in [0, n] have a prime number of set bits.
    int countUpTo(int n) {
        if (n < 0) return 0;
        const vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19};  // n < 2^20, so at most 20 set bits
        int width = 0;
        while ((n >> width) > 0) width++;
        // ways[a][b]: how many a-bit patterns have exactly b ones (Pascal's triangle)
        vector<vector<int>> ways(width + 1, vector<int>(width + 1, 0));
        for (int a = 0; a <= width; a++) {
            ways[a][0] = 1;
            for (int b = 1; b <= a; b++) ways[a][b] = ways[a - 1][b - 1] + ways[a - 1][b];
        }
        int total = 0, ones = 0;
        for (int i = width - 1; i >= 0; i--) {
            if ((n >> i) & 1) {
                // Put a 0 here instead: the i bits below can then be anything and stay below n.
                for (int p : primes)
                    if (p - ones >= 0 && p - ones <= i) total += ways[i][p - ones];
                ones++;  // keep this 1 and move on to the next bit
            }
        }
        for (int p : primes)
            if (p == ones) total++;  // n itself
        return total;
    }

public:
    int countPrimeSetBits(int left, int right) {
        return countUpTo(right) - countUpTo(left - 1);
    }
};
class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        return self.count_up_to(right) - self.count_up_to(left - 1)

    def count_up_to(self, n: int) -> int:
        """How many x in [0, n] have a prime number of set bits."""
        if n < 0:
            return 0
        primes = [2, 3, 5, 7, 11, 13, 17, 19]  # n < 2^20, so at most 20 set bits
        width = n.bit_length()
        # ways[a][b]: how many a-bit patterns have exactly b ones (Pascal's triangle)
        ways = [[0] * (width + 1) for _ in range(width + 1)]
        for a in range(width + 1):
            ways[a][0] = 1
            for b in range(1, a + 1):
                ways[a][b] = ways[a - 1][b - 1] + ways[a - 1][b]
        total, ones = 0, 0
        for i in range(width - 1, -1, -1):
            if (n >> i) & 1:
                # Put a 0 here instead: the i bits below can then be anything and stay below n.
                for p in primes:
                    if 0 <= p - ones <= i:
                        total += ways[i][p - ones]
                ones += 1  # keep this 1 and move on to the next bit
        if ones in primes:  # n itself
            total += 1
        return total
class Solution {
    private static final int[] PRIMES = {2, 3, 5, 7, 11, 13, 17, 19};  // n < 2^20, so at most 20 set bits

    public int countPrimeSetBits(int left, int right) {
        return countUpTo(right) - countUpTo(left - 1);
    }

    // How many x in [0, n] have a prime number of set bits.
    private int countUpTo(int n) {
        if (n < 0) return 0;
        int width = 32 - Integer.numberOfLeadingZeros(n);
        // ways[a][b]: how many a-bit patterns have exactly b ones (Pascal's triangle)
        int[][] ways = new int[width + 1][width + 1];
        for (int a = 0; a <= width; a++) {
            ways[a][0] = 1;
            for (int b = 1; b <= a; b++) ways[a][b] = ways[a - 1][b - 1] + ways[a - 1][b];
        }
        int total = 0, ones = 0;
        for (int i = width - 1; i >= 0; i--) {
            if (((n >> i) & 1) == 1) {
                // Put a 0 here instead: the i bits below can then be anything and stay below n.
                for (int p : PRIMES)
                    if (p - ones >= 0 && p - ones <= i) total += ways[i][p - ones];
                ones++;  // keep this 1 and move on to the next bit
            }
        }
        for (int p : PRIMES)
            if (p == ones) total++;  // n itself
        return total;
    }
}

Complexity Analysis

Let B be the number of bits in right, at most 20 here.

Time Complexity: O(B²). Pascal's triangle has at most 21 × 21 entries. The walk visits B bits and tries 8 primes at each, and it runs twice, once for right and once for left − 1. That is a few hundred small steps whatever the length of the range. A range of ten numbers and a range of a billion numbers cost the same.

Space Complexity: O(B²) for the triangle, at most 21 × 21 integers.

Within this problem's limits all three approaches finish in a fraction of a second. What this one changes is how the cost grows. The first two grow with the number of values in the range. This one grows only with the number of digits of right.