What is the best approach for the Sum of Values at Indices With K Set Bits problem?

The best approach is to iterate through the indices, counting set bits for each index. Using bitwise operations will improve the solution's efficiency.

How do I count set bits in a number?

You can count set bits by converting the number to its binary representation and counting the number of 1's, or by using bitwise operations for more efficiency.

Can this problem be optimized for large arrays?

Yes, using bitwise operations for counting set bits and avoiding unnecessary string conversions can significantly improve performance for larger arrays.

What should I do if k equals 0?

If k equals 0, you need to sum values at indices where the binary representation of the index has zero set bits (e.g., index 0).

What is the time complexity of the solution?

The time complexity is O(n * log(m)) where n is the array length and m is the number of bits in the largest index, though bitwise operations can optimize this to O(n).

#2859

Easy

auto_awesome数组·结合·位运算·操作

LeetCode 题解工作台

计算 K 置位下标对应元素的和

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。请你用整数形式返回 nums 中的特定元素之和，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。整数的二进制表示中的 1 就是这个整数的置位。例如， 21 的二进制表示为 10101 ，其中有 3 个置位。 …

数组位运算

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

请你用整数形式返回 nums 中的特定元素之和，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。

整数的二进制表示中的 1 就是这个整数的置位。

例如，21 的二进制表示为 10101 ，其中有 3 个置位。

示例 1：

输入：nums = [5,10,1,5,2], k = 1
输出：13
解释：下标的二进制表示是： 
0 = 000₂
1 = 001₂
2 = 010₂
3 = 011₂
4 = 100₂下标 1、2 和 4 在其二进制表示中都存在 k = 1 个置位。
因此，答案为 nums[1] + nums[2] + nums[4] = 13 。

示例 2：

输入：nums = [4,3,2,1], k = 2
输出：1
解释：下标的二进制表示是： 
0 = 00₂
1 = 01₂
2 = 10₂
3 = 11₂只有下标 3 的二进制表示中存在 k = 2 个置位。
因此，答案为 nums[3] = 1 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁵
0 <= k <= 10

lightbulb

解题思路

方法一：模拟

我们直接遍历每个下标 $i$ ，判断其二进制表示中 $1$ 的个数是否等于 $k$ ，如果等于则将其对应的元素累加到答案 $ans$ 中。

遍历结束后，返回答案即可。

时间复杂度 $O(n \times \log n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        return sum(x for i, x in enumerate(nums) if i.bit_count() == k)

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate correctly handles the bit counting and edge cases.
question_mark
Evaluate their approach to time and space optimization for larger arrays.
question_mark
Look for a clean and efficient solution using bitwise operations over string manipulation.

warning

常见陷阱

外企场景

error
Overcomplicating the solution by using string manipulations instead of bitwise operations.
error
Forgetting to handle edge cases such as k = 0 or very large indices.
error
Neglecting to optimize for large input sizes, which may cause time or space inefficiencies.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to sum values at indices with more than k set bits.
arrow_right_alt
Consider variations where the indices with exactly k set bits need to meet additional conditions (e.g., even or odd numbers).
arrow_right_alt
Instead of counting set bits, change the task to sum values at indices where the binary representation has exactly n 1's and n 0's.

help

常见问题

外企场景

继续练习

#2857 统计距离为 k 的点对 #2869 收集元素的最少操作次数 #2871 将数组分割成最多数目的子数组