LeetCode 2859 - Sum of Values at Indices With K Set Bits

LeetCode Problem 2859

Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem asks us to compute the sum of elements in an array, but not based on the values themselves. Instead, we decide whether to include an element by examining the binary representation of its index.

You are given a 0-indexed integer array nums and an integer k. For each index i in the array, we count how many 1 bits appear in the binary representation of i. If the number of set bits is exactly k, then nums[i] contributes to the final sum.

In simpler terms, we iterate through every position in the array and ask:

Does this index contain exactly k set bits in binary?

If the answer is yes, we add the corresponding value in nums to the result.

For example, suppose nums = [5,10,1,5,2] and k = 1.

The indices are:

• 0 → 0 in binary, 0 set bits
• 1 → 1 in binary, 1 set bit
• 2 → 10 in binary, 1 set bit
• 3 → 11 in binary, 2 set bits
• 4 → 100 in binary, 1 set bit

Only indices 1, 2, and 4 have exactly one set bit, so the answer becomes:

10 + 1 + 2 = 13

The constraints are relatively small:

• nums.length <= 1000
• nums[i] <= 10^5
• k <= 10

Since the array size is at most 1000, even a straightforward iteration over all indices is perfectly feasible. We do not need advanced optimization techniques.

There are several edge cases worth recognizing upfront. If k = 0, only indices with no set bits should be included, which means only index 0. If no index has exactly k set bits, the answer should naturally remain 0. Since the array is guaranteed to contain at least one element, we never need to worry about an empty input. Also, because k can be as large as 10, but indices may not contain that many bits, many cases may simply produce no matches.

Approaches

Brute Force Approach

The most direct solution is to iterate through every index in nums, convert the index into binary, count how many 1s appear, and check whether that count equals k.

For each index i, we determine its number of set bits. If it matches k, we add nums[i] to a running total.

This approach is correct because every valid index is checked exactly once, and the inclusion rule from the problem statement is applied precisely.

One possible implementation converts the index to a binary string and counts '1' characters:

bin(i).count('1')

However, repeatedly creating binary strings is unnecessary overhead.

Optimal Approach

A better approach still checks every index, but instead of converting numbers to strings, it uses a bit counting operation.

The key observation is that we only care about the number of set bits in an index. Modern languages provide efficient ways to count set bits directly.

In Python, we can use:

i.bit_count()

In Go, we can use:

bits.OnesCount(uint(i))

This avoids string conversion and uses efficient bit manipulation internally.

Since every index must still be examined once, the algorithm remains linear in the size of the array, but with cleaner and more efficient implementation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(log n)	Converts indices to binary strings and counts 1s
Optimal	O(n)	O(1)	Uses efficient built-in bit counting

Algorithm Walkthrough

1. Initialize a variable total_sum to 0.

This variable stores the running total of all valid elements whose indices contain exactly k set bits. 2. Iterate through the array using both the index and value.

We need access to the index because the decision depends on the index's binary representation, and we need the value to add into the answer. 3. Count the number of set bits in the current index.

For an index i, compute how many 1s appear in its binary representation. In Python, this can be done using i.bit_count(). In Go, bits.OnesCount(uint(i)) provides the same functionality. 4. Compare the set bit count with k.

If the count equals k, then this index satisfies the problem condition, so add the corresponding number to total_sum. 5. Continue until all indices are processed.

Since every index is examined exactly once, we guarantee no valid element is missed. 6. Return total_sum.

After the loop completes, the accumulated sum represents the required answer.

Why it works

The algorithm works because it evaluates every index exactly once and checks the exact condition required by the problem, whether the number of set bits equals k. Every qualifying element is added exactly once, and every non-qualifying element is ignored. Since the final result is the sum of precisely the valid elements, the algorithm is guaranteed to return the correct answer.

Python Solution

from typing import List

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        total_sum = 0

        for index, value in enumerate(nums):
            if index.bit_count() == k:
                total_sum += value

        return total_sum

The implementation follows the algorithm directly.

We begin by initializing total_sum to store the running answer. Then we iterate through the array using enumerate(nums), which gives us both the current index and the corresponding value.

For each index, we call index.bit_count() to determine how many set bits appear in its binary representation. If this count equals k, the value is added to the running total.

After processing all elements, the function returns total_sum.

This implementation is concise, efficient, and leverages Python's built-in bit counting method for clarity and performance.

Go Solution

package main

import "math/bits"

func sumIndicesWithKSetBits(nums []int, k int) int {
	totalSum := 0

	for index, value := range nums {
		if bits.OnesCount(uint(index)) == k {
			totalSum += value
		}
	}

	return totalSum
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built-in integer method like bit_count(), we use the math/bits package and call bits.OnesCount().

The index is converted to uint because OnesCount expects an unsigned integer type. Since indices are always non-negative, this conversion is completely safe.

There are no special concerns regarding nil versus empty slices because the problem guarantees at least one element. Integer overflow is also not a concern under the given constraints, because the maximum possible sum easily fits within Go's integer range.

Worked Examples

Example 1

Input:

nums = [5,10,1,5,2], k = 1

We iterate through each index and count set bits.

Index	Binary	Set Bits	nums[index]	Included?	Running Sum
0	0	0	5	No	0
1	1	1	10	Yes	10
2	10	1	1	Yes	11
3	11	2	5	No	11
4	100	1	2	Yes	13

Final answer:

13

Example 2

Input:

nums = [4,3,2,1], k = 2

Index	Binary	Set Bits	nums[index]	Included?	Running Sum
0	0	0	4	No	0
1	1	1	3	No	0
2	10	1	2	No	0
3	11	2	1	Yes	1

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is processed exactly once
Space	O(1)	Only a few variables are used

Although counting set bits takes time proportional to the number of machine bits, integer sizes are bounded and very small for the problem constraints. Therefore, each bit count operation is effectively constant time, making the overall complexity linear in the size of the array.

Test Cases

solution = Solution()

assert solution.sumIndicesWithKSetBits([5,10,1,5,2], 1) == 13  # Example 1
assert solution.sumIndicesWithKSetBits([4,3,2,1], 2) == 1  # Example 2

assert solution.sumIndicesWithKSetBits([7], 0) == 7  # Single element, index 0 qualifies
assert solution.sumIndicesWithKSetBits([7], 1) == 0  # Single element, no valid index

assert solution.sumIndicesWithKSetBits([1,2,3,4], 0) == 1  # Only index 0 has zero set bits
assert solution.sumIndicesWithKSetBits([1,2,3,4], 1) == 5  # Indices 1 and 2 qualify
assert solution.sumIndicesWithKSetBits([1,2,3,4], 3) == 0  # No matching indices

assert solution.sumIndicesWithKSetBits([10] * 1000, 1) > 0  # Large input stress test
assert solution.sumIndicesWithKSetBits([100000, 100000], 10) == 0  # k too large
assert solution.sumIndicesWithKSetBits([8,6,7,5,3,0,9], 2) == 8  # Multiple qualifying indices

Test	Why
[5,10,1,5,2], k=1	Validates the first provided example
[4,3,2,1], k=2	Validates the second provided example
[7], k=0	Tests smallest possible input
[7], k=1	Tests case where no index qualifies
[1,2,3,4], k=0	Ensures only index 0 is counted
[1,2,3,4], k=1	Tests multiple qualifying indices
[1,2,3,4], k=3	Verifies behavior when no matches exist
[10] * 1000, k=1	Stress test near maximum size
[100000,100000], k=10	Tests very large k
[8,6,7,5,3,0,9], k=2	Tests mixed qualifying indices

Edge Cases

Case 1: k = 0

This case can easily cause confusion because only numbers with zero set bits qualify. Since every positive index contains at least one set bit, the only valid index is 0.

For example:

nums = [5, 10, 20], k = 0

Only index 0 qualifies, so the answer is 5. The implementation handles this naturally because 0.bit_count() returns 0.

Case 2: No Matching Indices

There may be situations where no index contains exactly k set bits.

For example:

nums = [1,2,3], k = 5

No index in this small array has five set bits, so the loop never adds anything to total_sum. Since the sum starts at 0, the correct answer is returned automatically.

Case 3: Single Element Array

The smallest valid input contains only one number.

For example:

nums = [42]

The only index is 0, whose binary representation contains zero set bits. If k = 0, the answer should be 42; otherwise, it should be 0.

The implementation handles this correctly because the loop simply processes one element and applies the same rule consistently.