[LeetCode] 2859. Sum of Values at Indices With K Set Bits

You are given a 0-indexed integer array nums and an integer k.

Return an integer that denotes the sum of elements in nums whose corresponding indices have exactly k set bits in their binary representation.

The set bits in an integer are the 1’s present when it is written in binary.

For example, the binary representation of 21 is 10101, which has 3 set bits.

Example 1:
Input: nums = [5,10,1,5,2], k = 1
Output: 13
Explanation: The binary representation of the indices are:
0 = 0002
1 = 0012
2 = 0102
3 = 0112
4 = 1002
Indices 1, 2, and 4 have k = 1 set bits in their binary representation.
Hence, the answer is nums[1] + nums[2] + nums[4] = 13.

Example 2:
Input: nums = [4,3,2,1], k = 2
Output: 1
Explanation: The binary representation of the indices are:
0 = 002
1 = 012
2 = 102
3 = 112
Only index 3 has k = 2 set bits in its binary representation.
Hence, the answer is nums[3] = 1.

Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 105
0 <= k <= 10

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

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

思路

对于数组内的每一个数字，我们看一下数字的二进制表达里有几个 1，如果当前数字的二进制表达里 1 的个数等于这个数字在 input 数组内的下标，则把这个数字累加到结果里。

计算数字的二进制表达里有几个 1 等同于 191 题。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int res = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (helper(i) == k) {
                res += nums.get(i);
            }
        }
        return res;
    }

    public int helper(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
        return count;
    }
}

相关题目

191. Number of 1 Bits
2859. Sum of Values at Indices With K Set Bits