Skip to content

2859. Sum of Values at Indices With K Set Bits

Description

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

Solutions

Solution 1: Simulation

We directly traverse each index \(i\), and check whether the number of \(1\)s in its binary representation is equal to \(k\). If it is, we add the corresponding element to the answer \(ans\).

After the traversal ends, we return the answer.

The time complexity is \(O(n \times \log n)\), where \(n\) is the length of the array \(nums\). The space complexity is \(O(1)\).

1
2
3
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (Integer.bitCount(i) == k) {
                ans += nums.get(i);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int sumIndicesWithKSetBits(vector<int>& nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (__builtin_popcount(i) == k) {
                ans += nums[i];
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func sumIndicesWithKSetBits(nums []int, k int) (ans int) {
    for i, x := range nums {
        if bits.OnesCount(uint(i)) == k {
            ans += x
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function sumIndicesWithKSetBits(nums: number[], k: number): number {
    let ans = 0;
    for (let i = 0; i < nums.length; ++i) {
        if (bitCount(i) === k) {
            ans += nums[i];
        }
    }
    return ans;
}

function bitCount(n: number): number {
    let count = 0;
    while (n) {
        n &= n - 1;
        count++;
    }
    return count;
}

Comments