You are given a 0-indexed integer array nums and an integer k.
Return an integer that denotes the sum of elements in nums whose corresponding indices have exactly k set bits in their binary representation.
The set bits in an integer are the 1's present when it is written in binary.
21 is 10101, which has 3 set bits.
Example 1:
Input: nums = [5,10,1,5,2], k = 1 Output: 13 Explanation: The binary representation of the indices are: 0 = 0002 1 = 0012 2 = 0102 3 = 0112 4 = 1002 Indices 1, 2, and 4 have k = 1 set bits in their binary representation. Hence, the answer is nums[1] + nums[2] + nums[4] = 13.
Example 2:
Input: nums = [4,3,2,1], k = 2 Output: 1 Explanation: The binary representation of the indices are: 0 = 002 1 = 012 2 = 102 3 = 112 Only index 3 has k = 2 set bits in its binary representation. Hence, the answer is nums[3] = 1.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1050 <= k <= 10Problem 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.
This approach involves iterating through each index of the given array and counting the set bits in its binary representation. If the count matches k, add the value at that index to the sum.
This C solution defines a helper function countSetBits that counts the number of set bits in the binary representation of a given number. In the main function sumOfValuesAtIndexes, we iterate over the indices of the array, check the set bits, and add the array values accordingly.
Time Complexity: O(n * log(m)), where n is the length of the array and m is the maximum index value.
Space Complexity: O(1)
By using built-in functions, we can optimize the process of counting set bits in binary representations. Most modern programming languages provide a bit-counting technique, often called popcount, which allows faster set-bit counting.
In this optimized Python solution, we directly use bin().count('1') to calculate the number of set bits. This avoids manual iteration over the bits of an integer.
Python
JavaScript
Java
Time Complexity: O(n * m), where n is the length of the array and m is the bit length of the maximum index value.
Space Complexity: O(1)
We directly traverse each index i, and check whether the number of 1s in its binary representation is equal to k. If it is, we add the corresponding element to the answer ans.
After the traversal ends, we return the answer.
The time complexity is O(n times log n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * log(m)), where n is the length of the array and m is the maximum index value. |
| Optimized Popcount Approach | Time Complexity: O(n * m), where n is the length of the array and m is the bit length of the maximum index value. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Bit Counting | O(n log n) | O(1) | When implementing bit counting manually or explaining the binary logic in interviews |
| Built-in Popcount | O(n) | O(1) | Preferred practical solution using optimized language bit-count functions |
Leetcode 2859 Sum of Values at Indices With K Set Bits • Tech Diet • 1,731 views views
Watch 9 more video solutions →Practice Sum of Values at Indices With K Set Bits with our built-in code editor and test cases.
Practice on FleetCode