Sum of Values at Indices With K Set Bits
EasyPrompt
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.
- For example, the binary representation of
21is10101, which has3set 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 <= 10
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each index of the array. For each index, it converts the number to its binary string representation and then counts the occurrences of the character '1'. If this count matches k, the corresponding element from nums is added to the total sum.
Algorithm
- Initialize a variable
sumto 0. - Iterate with an index
ifrom 0 tonums.size() - 1. - For each index
i, convert it to a binary string usingInteger.toBinaryString(i). - Initialize a
setBitsCountto 0. - Iterate through each character of the binary string. If the character is '1', increment
setBitsCount. - If the final
setBitsCountis equal tok, add the valuenums.get(i)tosum. - After the loop finishes, return the final
sum.
Walkthrough
This is a straightforward brute-force method. The core idea is to loop through every index from 0 to nums.size() - 1. In each iteration, we need to determine if the index has k set bits. We accomplish this by first converting the integer index to its binary string equivalent (e.g., 5 becomes "101"). Then, we iterate over this string, character by character, counting how many '1's we find. If this count equals the target k, we add the element at that index, nums.get(i), to our running total.
import java.util.List; class Solution { public int sumIndicesWithKSetBits(List<Integer> nums, int k) { int sum = 0; for (int i = 0; i < nums.size(); i++) { String binaryString = Integer.toBinaryString(i); int setBitsCount = 0; for (char c : binaryString.toCharArray()) { if (c == '1') { setBitsCount++; } } if (setBitsCount == k) { sum += nums.get(i); } } return sum; }}Complexity
Time
O(N * log N), where N is the length of the `nums` array. The outer loop runs N times. Inside the loop, converting an integer `i` to a binary string takes O(log i) time, and then iterating through the string to count bits also takes O(log i) time.
Space
O(log N), where N is the length of the `nums` array. This space is required to store the binary string representation of the largest index, which has a length of O(log N).
Trade-offs
Pros
Easy to understand and implement for beginners.
The logic directly follows the problem statement.
Cons
Inefficient due to the overhead of creating and iterating through strings for each number.
Higher space complexity compared to bit manipulation approaches.
This method improves upon the first by avoiding string conversion. It directly counts the set bits of each index using a bit manipulation trick known as Brian Kernighan's algorithm. This algorithm is efficient because it iterates only as many times as there are set bits. It works by repeatedly unsetting the rightmost set bit of a number (n = n & (n - 1)) until the number becomes zero, counting the number of operations.
Algorithm
- Initialize a variable
sumto 0. - Iterate with an index
ifrom 0 tonums.size() - 1. - For each index
i, define a helper function or inline logic to count its set bits using Brian Kernighan's algorithm. - To count bits for a number
n:- Initialize
count = 0. - While
n > 0, repeatedly apply the operationn = n & (n - 1)and incrementcount.
- Initialize
- If the returned count is equal to
k, add the valuenums.get(i)tosum. - After the loop, return
sum.
Walkthrough
Instead of the costly process of converting numbers to strings, we can use bitwise operations for a more performant solution. Brian Kernighan's algorithm is a classic technique for counting set bits. The key insight is that for any number n, the operation n & (n - 1) unsets the least significant set bit (the rightmost '1'). By repeatedly applying this operation in a loop until n becomes 0, we can count exactly how many set bits were originally present. We apply this counting method to each index i and add nums.get(i) to the sum if the bit count equals k.
import java.util.List; class Solution { private int countSetBits(int n) { int count = 0; while (n > 0) { n &= (n - 1); // This clears the least significant set bit count++; } return count; } public int sumIndicesWithKSetBits(List<Integer> nums, int k) { int sum = 0; for (int i = 0; i < nums.size(); i++) { if (countSetBits(i) == k) { sum += nums.get(i); } } return sum; }}Complexity
Time
O(N * log N), where N is the length of `nums`. The outer loop runs N times. The inner bit-counting loop runs as many times as there are set bits in `i`, which is at most O(log i). While asymptotically the same as the string approach, it's significantly faster in practice.
Space
O(1), as it only uses a few variables for calculation, requiring no extra space that scales with the input size.
Trade-offs
Pros
More efficient than string conversion as it uses fast, low-level bitwise operations.
Constant space complexity.
Cons
Still involves a sub-loop for each number, making it less performant than a single-instruction built-in function.
This is the most efficient and concise approach. Most programming languages provide a built-in function to count the number of set bits in an integer's binary representation. In Java, Integer.bitCount() can be used. This function is highly optimized and often maps to a single, fast machine instruction (like popcnt on modern CPUs), making the bit counting an effectively constant-time operation.
Algorithm
- Initialize a variable
sumto 0. - Iterate with an index
ifrom 0 tonums.size() - 1. - Use the built-in function
Integer.bitCount(i)to get the number of set bits for the indexiin a single step. - If the result of
Integer.bitCount(i)is equal tok, add the valuenums.get(i)tosum. - After the loop finishes, return the final
sum.
Walkthrough
The optimal solution leverages the standard library's built-in capabilities. Java's Integer.bitCount(int i) method is specifically designed for this purpose. It returns the number of one-bits (also known as the population count) in the two's complement binary representation of an int value. This function is implemented with highly optimized, often hardware-level, instructions. By using this function, we can simplify our code and achieve the best possible performance. The overall algorithm remains the same: iterate through indices, but the check for k set bits becomes a single, efficient function call.
import java.util.List; class Solution { public int sumIndicesWithKSetBits(List<Integer> nums, int k) { int sum = 0; for (int i = 0; i < nums.size(); i++) { if (Integer.bitCount(i) == k) { sum += nums.get(i); } } return sum; }}Complexity
Time
O(N), where N is the length of the `nums` array. The loop runs N times, and `Integer.bitCount()` is effectively a constant time operation, O(1), as it operates on a fixed-size integer (32 bits).
Space
O(1), as no extra space proportional to the input size is required.
Trade-offs
Pros
Most efficient in terms of time complexity.
Code is clean, concise, and easy to read.
Leverages platform-specific optimizations for maximum speed.
Cons
Relies on the availability of a specific built-in function in the programming language, which might not be present in all environments.
Solutions
Solution
class Solution {public int sumIndicesWithKSetBits(List<Integer> nums, int k) { int ans = 0; for (int i = 0; i < nums.size(); i++) { if (Integer.bitCount(i) == k) { ans += nums.get(i); } } return ans; }}class Solution {public: int sumIndicesWithKSetBits(vector<int> &nums, int k) { int ans = 0; for (int i = 0; i < nums.size(); ++i) { if (__builtin_popcount(i) == k) { ans += nums[i]; } } return ans; }};class Solution: def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int: return sum( x for i, x in enumerate(nums) if i . bit_count() == k)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.