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.
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; }}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.