Sum of Values at Indices With K Set Bits - Video Solutions

Problem Overview: You are given an array nums and an integer k. Each index has a binary representation. The task is to sum all values nums[i] where the index i contains exactly k set bits (1s) in its binary form.

This problem combines basic array traversal with a small piece of bit manipulation. The main work is counting how many 1s appear in the binary representation of each index.

Approach 1: Brute Force Bit Counting (O(n log n) time, O(1) space)

Iterate through every index of the array and manually count the number of set bits in that index. You can do this by repeatedly shifting the number right (i >> 1) and checking the lowest bit using i & 1. If the total number of set bits equals k, add nums[i] to the running sum. This approach performs a small loop for every index to compute the bit count.

The complexity depends on how many bits the index has. Counting bits for a number takes up to O(log n) operations, and you perform it for all n indices, giving O(n log n) time overall. Space stays O(1) because only a few counters are used. This version is easy to implement and clearly demonstrates the mechanics of binary bit counting.

Approach 2: Built-in Popcount (O(n) time, O(1) space)

Most languages provide a built-in popcount operation that directly returns the number of set bits in an integer. Examples include Integer.bitCount() in Java, bin(i).count('1') or int.bit_count() in Python, and similar helpers in JavaScript. Instead of manually shifting bits, call this function for each index.

Loop through the array indices from 0 to n-1, compute the set bit count using the built-in function, and compare it with k. When they match, add nums[i] to the result. Because popcount is implemented using optimized CPU instructions, the operation is effectively constant time.

The full traversal still requires visiting every element once, giving O(n) time and O(1) extra space. This approach is concise, readable, and typically faster than manual bit counting.

Recommended for interviews: Start by describing the brute force bit-counting idea to show you understand how binary representation works. Then switch to the popcount approach as the practical solution. Interviewers usually expect the O(n) iteration combined with a built-in or optimized bit-count operation, since the real challenge here is recognizing that only the index's set bits matter.