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

🟢 🔖 位运算 数学 🔗 力扣open in new window LeetCodeopen in new window

题目

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 <= 10^6
0 <= right - left <= 10^4

题目大意

给你两个整数 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^6
0 <= right - left <= 10^4

解题思路

计算一个数的二进制中 1 的个数：
- 通过位运算 n & 1 判断最低位是否为 1，然后使用右移操作 n >>= 1 移除最低位，重复直到 n 为 0。
- 累加过程中统计 1 的个数。
判断 1 的个数是否为质数：
- 使用一个固定的集合 set 存储小于 20 的所有质数（因为数字上限为 10^6，二进制 1 的个数最多为 19）。
- 直接查找集合判断是否是质数。
遍历范围 [left, right]：
- 对于每个数，计算其二进制中 1 的个数，判断是否在集合中，如果是则累加结果。

复杂度分析

时间复杂度：O(m * log n)
- 其中 m = right - left，遍历范围 [left, right]，需要 O(m)。
- 对每个数字调用 getSetBits，复杂度为 O(log n)，其中 n 为当前数字的大小。
- 因此总时间复杂度为：O(m * log n)。
空间复杂度：O(1)，使用了一个固定大小的集合存储质数，复杂度为 O(1)。

代码

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var countPrimeSetBits = function (left, right) {
	// 辅助函数：计算一个数字的二进制中 1 的个数
	const getSetBits = function (n) {
		let res = 0;
		while (n) {
			res += n & 1; // 统计最低位是否为 1
			n >>= 1; // 右移，移除最低位
		}
		return res; // 返回二进制中 1 的个数
	};

	let set = new Set([2, 3, 5, 7, 11, 13, 17, 19]);

	let res = 0;

	for (let i = left; i <= right; i++) {
		// 获取二进制中 1 的个数
		const setBits = getSetBits(i);
		// 判断是否为质数
		if (set.has(setBits)) {
			res++;
		}
	}

	return res;
};

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

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

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

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

题目

题目大意

解题思路

复杂度分析

代码

相关题目