762. 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.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

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)

Example 2:

Input: L = 10, R = 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)

Note:

1. L, R will be integers L <= R in the range [1, 10^6].
2. R - L will be at most 10000.

Problem Summary #

Given two integers L and R, find the number of integers in the closed interval [L, R] whose number of set bits is prime. (Note that set bits represent the number of 1s in the binary representation. For example, the binary representation of 21 is 10101, which has 3 set bits. Also, 1 is not a prime number.)

Note:

• L, R are integers with L <= R and in [1, 10^6].
• The maximum value of R - L is 10000.

Solution Ideas #

• The problem gives the interval [L, R]. For each integer in this interval, if the number of 1s in its binary representation is a prime number, then add one to the final result. What is the final result? This problem is a combination problem. Determining how many 1 bits a number has is problem 191. The problem limits the maximum interval value to no more than 10^6, so the maximum number of 1 bits is 19, which means the largest prime number is 19. Therefore, the prime numbers can be enumerated finitely. Finally, just accumulate the result according to the meaning of the problem.

Code #

package leetcode

import "math/bits"

func countPrimeSetBits(L int, R int) int {
	counter := 0
	for i := L; i <= R; i++ {
		if isPrime(bits.OnesCount(uint(i))) {
			counter++
		}
	}
	return counter
}

func isPrime(x int) bool {
	return x == 2 || x == 3 || x == 5 || x == 7 || x == 11 || x == 13 || x == 17 || x == 19
}