problemeasyalgorithmsleetcode-2859leetcode 2859leetcode2859

Sum of Values at Indices With K Set Bits

EasyUpdated: Oct 13, 2025
Practice on:
LeetCode

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

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] <= 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

C++
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

Java
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
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
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
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
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)

Comments