Problem

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

Return _an integer that denotes thesum of elements in _nums _whose correspondingindices 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5
6
7
8
9

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] <= 10^5
  • 0 <= k <= 10

Solution

Approach

For each index, count the number of set bits in its binary representation. If it equals k, add nums[i] to the answer.

Code

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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;
    }
};
Java
1
2
3
4
5
6
7
8
9

class Solution {
    public int sumIndicesWithKSetBits(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (Integer.bitCount(i) == k) ans += nums[i];
        }
        return ans;
    }
}
Kotlin
1
2
3
4
5
6
7
8
9

class Solution {
    fun sumIndicesWithKSetBits(nums: IntArray, k: Int): Int {
        var ans = 0
        for (i in nums.indices) {
            if (i.countOneBits() == k) ans += nums[i]
        }
        return ans
    }
}
Python
1
2
3

class Solution:
    def sumIndicesWithKSetBits(self, nums: list[int], k: int) -> int:
        return sum(x for i, x in enumerate(nums) if bin(i).count('1') == k)
Rust
1
2
3
4
5

impl Solution {
    pub fn sum_indices_with_k_set_bits(nums: Vec<i32>, k: i32) -> i32 {
        nums.into_iter().enumerate().filter(|(i,_)| i.count_ones() == k as u32).map(|(_,x)| x).sum()
    }
}
TypeScript
1
2
3
4
5
6
7

function sumIndicesWithKSetBits(nums: number[], k: number): number {
    let ans = 0;
    for (let i = 0; i < nums.length; ++i) {
        if (i.toString(2).split('1').length - 1 === k) ans += nums[i];
    }
    return ans;
}

Explanation

We check the number of set bits for each index and sum the values at those indices where the count matches k.

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)