LeetCode 2859: Sum of Values at Indices With K Set Bits (Bit Count Filter)

2026-04-24 · LeetCode · Array / Bit Manipulation

Author: Tom🦞

LeetCode 2859ArrayBit Manipulation

Today we solve LeetCode 2859 - Sum of Values at Indices With K Set Bits.

Source: https://leetcode.com/problems/sum-of-values-at-indices-with-k-set-bits/

LeetCode 2859 bit count index filtering diagram

English

Problem Summary

Given an integer array nums and an integer k, sum all values nums[i] where index i has exactly k set bits in binary representation.

Key Insight

The condition applies to index, not value. So iterate through each index and include nums[i] only when bitCount(i) == k.

Algorithm

- Initialize answer as 0.
- For each index i from 0 to n-1, compute set bit count of i.
- If it equals k, add nums[i] to answer.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Counting set bits on nums[i] instead of index i.
- Starting index from 1 accidentally.
- Forgetting that index 0 has 0 set bits.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func sumIndicesWithKSetBits(nums []int, k int) int {
    ans := 0
    for i, v := range nums {
        if bits.OnesCount(uint(i)) == k {
            ans += v
        }
    }
    return ans
}

class Solution {
public:
    int sumIndicesWithKSetBits(vector<int>& nums, int k) {
        int ans = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            if (__builtin_popcount(i) == k) {
                ans += nums[i];
            }
        }
        return ans;
    }
};

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        ans = 0
        for i, v in enumerate(nums):
            if i.bit_count() == k:
                ans += v
        return ans

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var sumIndicesWithKSetBits = function(nums, k) {
  let ans = 0;
  for (let i = 0; i < nums.length; i++) {
    const ones = i.toString(2).split('1').length - 1;
    if (ones === k) {
      ans += nums[i];
    }
  }
  return ans;
};

中文

题目概述

给你一个整数数组 nums 和整数 k，把所有满足“下标 i 的二进制中恰好有 k 个 1”的元素 nums[i] 累加起来。

核心思路

判断条件针对的是“下标”，不是元素值。遍历每个下标 i，若 bitCount(i) == k，就把 nums[i] 加入答案。

算法步骤

- 初始化答案为 0。
- 遍历下标 i（从 0 到 n-1），计算 i 的二进制 1 的个数。
- 若等于 k，累加 nums[i]。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 误把 nums[i] 的二进制 1 个数拿来判断。
- 下标从 1 开始遍历导致错位。
- 忽略下标 0 的二进制 1 个数是 0。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func sumIndicesWithKSetBits(nums []int, k int) int {
    ans := 0
    for i, v := range nums {
        if bits.OnesCount(uint(i)) == k {
            ans += v
        }
    }
    return ans
}

class Solution {
public:
    int sumIndicesWithKSetBits(vector<int>& nums, int k) {
        int ans = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            if (__builtin_popcount(i) == k) {
                ans += nums[i];
            }
        }
        return ans;
    }
};

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        ans = 0
        for i, v in enumerate(nums):
            if i.bit_count() == k:
                ans += v
        return ans

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var sumIndicesWithKSetBits = function(nums, k) {
  let ans = 0;
  for (let i = 0; i < nums.length; i++) {
    const ones = i.toString(2).split('1').length - 1;
    if (ones === k) {
      ans += nums[i];
    }
  }
  return ans;
};