Sum of Values at Indices With K Set Bits — Easy Problem & Solution

Problem statement

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

Return the sum of nums[i] over every index i whose binary representation contains exactly k set bits (ones). The values in nums are irrelevant to the test — only the index matters.

Example 1

Input: nums = [5,10,1,5,2], k = 1
Output: 13
Explanation: Indices with one set bit are 1 (binary 1), 2 (binary 10) and 4 (binary 100): 10 + 1 + 2 = 13.

Example 2

Input: nums = [4,3,2,1], k = 2
Output: 1
Explanation: Only index 3 (binary 11) has two set bits.

Example 3

Input: nums = [9,8,7], k = 0
Output: 9
Explanation: Index 0 is the only index with no set bits.

Constraints

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 100000
• 0 <= k <= 10

How to solve Sum of Values at Indices With K Set Bits

The filter is a property of the index, so walk the indices, count the ones in each index's binary form, and add the value when the count matches.

Approach

1. Write a helper that counts set bits: while x > 0, add x & 1 and shift x right by one.
2. Loop i from 0 to n - 1.
3. When the helper returns k, add nums[i] to the running total.

Why it works

Every index is tested exactly once against the exact predicate the statement gives, so the total is the sum over precisely the qualifying indices.

Complexity

• Time — O(n log n) — the bit loop runs at most log n times per index
• Space — O(1)

Pitfalls

• Counting the bits of nums[i] instead of i — the values are deliberately noisy to punish that.
• A while (x) loop that shifts a negative number never ends; indices are non-negative, so this is safe here but worth knowing.

Reference solution

Python

from typing import List

def sumIndicesWithKSetBits(nums: List[int], k: int) -> int:
    total = 0
    for i, v in enumerate(nums):
        if bin(i).count("1") == k:
            total += v
    return total

JavaScript

var sumIndicesWithKSetBits = function(nums, k) {
    var total = 0;
    for (var i = 0; i < nums.length; i++) {
        var x = i, c = 0;
        while (x > 0) { c += x & 1; x >>= 1; }
        if (c === k) total += nums[i];
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy