Prime Number of Set Bits in Binary Representation

Easy
419.

Prime Number of Set Bits in Binary Representation

Prime Number of Set Bits in Binary Representation is an easy coding problem on math and bit manipulation, asked in Amazon and Adobe interviews.

Given two integers left and right, return the count of numbers in the inclusive range [left, right] whose number of set bits is a prime number.

Example 1

Input
left = 6, right = 10
Output
4
Explanation
6, 9 and 10 have two set bits; 7 has three.

Example 2

Input
left = 10, right = 15
Output
5

Example 3

Input
left = 1, right = 1
Output
0

Constraints

  • 1 <= left <= right <= 20000
  • right - left <= 200
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var countPrimeSetBits = function(left, right) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Prime Number of Set Bits in Binary Representation — Solution

Prime Number of Set Bits in Binary Representation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Prime Number of Set Bits in Binary Representation is an easy coding problem on math and bit manipulation, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Math, Bit Manipulation
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given two integers left and right, return the count of numbers in the inclusive range [left, right] whose number of set bits is a prime number.

Example 1

Input: left = 6, right = 10
Output: 4
Explanation: 6, 9 and 10 have two set bits; 7 has three.

Example 2

Input: left = 10, right = 15
Output: 5

Example 3

Input: left = 1, right = 1
Output: 0

Constraints

  • 1 <= left <= right <= 20000
  • right - left <= 200

Hints for Prime Number of Set Bits in Binary Representation

  1. Hint 1

    Count the set bits of each number in the range.

  2. Hint 2

    That count is small — under 20 — so the primality test is trivial.

  3. Hint 3

    You can even hard-code the set of primes below 20 and check membership.

How to solve Prime Number of Set Bits in Binary Representation

Count set bits of each number in the range and test membership in the small set of primes below 20.

Approach

  1. For each v in [left, right], compute its popcount.
  2. Count those whose popcount is in {2, 3, 5, 7, 11, 13, 17, 19}.

Why it works

A 32-bit number has at most 32 set bits and the constraints keep it under 20, so a hard-coded prime set suffices.

Complexity

  • Time — O((right - left) · log right)
  • Space — O(1)

Pitfalls

  • 1 is not prime — a power of two does not count.

Reference solution

Python

def countPrimeSetBits(left: int, right: int) -> int:
    primes = {2, 3, 5, 7, 11, 13, 17, 19}
    return sum(1 for v in range(left, right + 1) if bin(v).count("1") in primes)

Java

public static int countPrimeSetBits(int left, int right) {
    Set<Integer> primes = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19));
    int count = 0;
    for (int v = left; v <= right; v++) {
        if (primes.contains(Integer.bitCount(v))) count++;
    }
    return count;
}

C++

int countPrimeSetBits(int left, int right) {
    unordered_set<int> primes = {2, 3, 5, 7, 11, 13, 17, 19};
    int count = 0;
    for (int v = left; v <= right; v++) {
        int bits = 0;
        unsigned int x = (unsigned int) v;
        while (x) {
            bits += (int) (x & 1u);
            x >>= 1;
        }
        if (primes.count(bits) > 0) count++;
    }
    return count;
}

JavaScript

var countPrimeSetBits = function(left, right) {
    const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19]);
    let count = 0;
    for (let v = left; v <= right; v++) {
        let bits = 0;
        let x = v;
        while (x > 0) {
            bits += x & 1;
            x >>>= 1;
        }
        if (primes.has(bits)) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Bit Manipulation