Skip to main content
Talentd

Sum of Values at Indices With K Set Bits - Solution & Explanation

EasyArrayBit Manipulation12 min readAsked at: Accenture
Practice this problem

Problem Statement

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 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 <= 1000
  • 1 <= nums[i] <= 105
  • 0 <= k <= 10

Approach Overview

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.

Approach 1: Brute Force Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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)

Try this approach in the editor →

Approach 2: Optimized Popcount Approach

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.

Code

PythonJavaScriptJava

Python

JavaScript

Java

Complexity

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)

Try this approach in the editor →

Approach 3: Simulation

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

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)

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.
Space Complexity: O(1)

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Bit CountingO(n log n)O(1)When implementing bit counting manually or explaining the binary logic in interviews
Built-in PopcountO(n)O(1)Preferred practical solution using optimized language bit-count functions

Video Solution

Leetcode 2859 Sum of Values at Indices With K Set Bits • Tech Diet • 1,733 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of Values at Indices With K Set Bits easy or hard?
LeetCode classifies this problem as Easy. It mainly tests understanding of array traversal and counting set bits in integers, which are foundational concepts in bit manipulation.
Sum of Values at Indices With K Set Bits Python/Java solution
In Python, iterate over indices and use i.bit_count() or bin(i).count('1') to check if the number of set bits equals k. In Java, use Integer.bitCount(i). If the condition matches, add nums[i] to the running sum. Both implementations run in O(n) time.
How to solve Sum of Values at Indices With K Set Bits in O(n)?
Traverse the array from index 0 to n-1 and compute the number of set bits in each index using a popcount function such as int.bit_count() in Python or Integer.bitCount() in Java. If the count equals k, add nums[i] to the result. This single pass gives an O(n) solution.
What is the best approach for Sum of Values at Indices With K Set Bits?
The most efficient approach iterates through the array once and uses a popcount operation to count the number of set bits in each index. If the bit count equals k, add nums[i] to the sum. This runs in O(n) time with O(1) extra space because each index is processed once.
Is Sum of Values at Indices With K Set Bits asked at Google/Amazon/Meta?
This problem is categorized as an Easy array and bit manipulation question. Similar bit-counting problems frequently appear in coding interviews at companies like Amazon, Google, and Meta to test familiarity with binary operations and basic iteration patterns.
What data structure is used in Sum of Values at Indices With K Set Bits?
The primary data structure is an array. The algorithm simply iterates through array indices and uses bit manipulation techniques to evaluate the binary representation of each index.
What is the time complexity of Sum of Values at Indices With K Set Bits?
The optimal solution runs in O(n) time and O(1) space. Each array index is visited once, and the number of set bits is calculated using a constant-time popcount operation provided by most programming languages.

Ready to solve this problem?

Practice Sum of Values at Indices With K Set Bits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Counting Bits

Next

Find the K-or of an Array