Sum of Values at Indices With K Set Bits — Solution
Sum of Values at Indices With K Set Bits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Sum of Values at Indices With K Set Bits is an easy coding problem on arrays and bit manipulation, asked in Adobe and Zoho interviews.
- Difficulty: Easy
- Topics: Arrays, Bit Manipulation
- Asked at: Adobe, Zoho
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 10001 <= nums[i] <= 1000000 <= k <= 10
Hints for Sum of Values at Indices With K Set Bits
Hint 1
Iterate over indices, not values — the condition is a property of
i.Hint 2
Counting set bits is a loop of
x & 1followed byx >>= 1.Hint 3
k = 0selects exactly one index: zero.
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
- Write a helper that counts set bits: while
x > 0, addx & 1and shiftxright by one. - Loop
ifrom0ton - 1. - When the helper returns
k, addnums[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 ofi— 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 totalJava
public static int sumIndicesWithKSetBits(int[] nums, int k) {
int total = 0;
for (int i = 0; i < nums.length; i++) {
if (Integer.bitCount(i) == k) total += nums[i];
}
return total;
}C++
int sumIndicesWithKSetBits(vector<int>& nums, int k) {
int total = 0;
for (int i = 0; i < (int) nums.size(); i++) {
if (__builtin_popcount((unsigned) i) == k) total += nums[i];
}
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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation