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

Method 1 - Count Set Bits (Enumerate Indices)

Intuition

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

Approach

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

Code

 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;
    }
};

Code

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;
    }
}
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
    }
}
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)
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()
    }
}
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;
}

Complexity

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