How do I count set bits in a number?

You can count the set bits using bitwise operations, such as repeatedly shifting the number and applying a mask, or by using a built-in function like Python's bin(x).count('1').

What prime numbers should I check for?

You only need to check for prime numbers that are less than or equal to the maximum possible number of set bits. For most cases, these primes are 2, 3, 5, 7, 11, 13, 17, and a few others.

How can I optimize this solution for large ranges?

Precompute a list of prime numbers and use it to quickly check the primality of the set bit counts. Also, avoid redundant checks for numbers with the same number of set bits.

Can I use a built-in function to check primality?

Yes, many languages have built-in functions to check if a number is prime. You can also use libraries like math.isprime in Python.

What if the range size is very small?

For small ranges, a straightforward approach works fine. However, always keep efficiency in mind for larger ranges.

#762

Easy

auto_awesome数学·位运算

LeetCode 题解工作台

二进制表示中质数个计算置位

给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回计算置位位数为质数的整数个数。计算置位位数就是二进制表示中 1 的个数。例如， 21 的二进制表示 10101 有 3 个计算置位。示例 1：输入： left = 6, right = 1…

数学位运算

题目描述

给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。

计算置位位数 就是二进制表示中 1 的个数。

例如， 21 的二进制表示 10101 有 3 个计算置位。

示例 1：

输入：left = 6, right = 10
输出：4
解释：
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)
共计 4 个计算置位为质数的数字。

示例 2：

输入：left = 10, right = 15
输出：5
解释：
10 -> 1010 (2 个计算置位, 2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)
共计 5 个计算置位为质数的数字。

提示：

1 <= left <= right <= 10⁶
0 <= right - left <= 10⁴

lightbulb

解题思路

方法一：数学 + 位运算

题目中 $\textit{left}$ 和 $\textit{right}$ 的范围均在 $10^6$ 以内，而 $2^{20} = 1048576$ ，因此，二进制中 $1$ 的个数最多也就 $20$ 个，而 $20$ 以内的质数有 $[2, 3, 5, 7, 11, 13, 17, 19]$ 。

我们枚举 $[\textit{left},.. \textit{right}]$ 范围内的每个数，统计其二进制中 $1$ 的个数，然后判断该个数是否为质数，如果是，答案加一。

时间复杂度 $O(n\times \log m)$ 。其中 $n = \textit{right} - \textit{left} + 1$ ，而 $m$ 为 $[\textit{left},.. \textit{right}]$ 范围内的最大数。

1

2

3

4

5

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        return sum(i.bit_count() in primes for i in range(left, right + 1))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should focus on efficiently counting set bits and checking for primality.
question_mark
A focus on optimization is important, especially with the constraint that the range length can be up to 10,000.
question_mark
The candidate should ensure their solution handles the range limits appropriately and avoids unnecessary calculations.

warning

常见陷阱

外企场景

error
Incorrectly counting the number of set bits, leading to wrong results.
error
Inefficient primality testing, especially when checking large numbers repeatedly.
error
Overlooking edge cases like the smallest and largest numbers in the range.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement a solution using bit manipulation to count set bits.
arrow_right_alt
Consider handling larger ranges more efficiently using precomputed prime numbers.
arrow_right_alt
Optimize for cases where the difference between right and left is small, improving performance.

help

常见问题

外企场景

继续练习

#779 第K个语法符号 #782 变为棋盘 #805 数组的均值分割