2859. Sum of Values at Indices With K Set Bits Solution

The problem

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 = 000₂
1 = 001₂
2 = 010₂
3 = 011₂
4 = 100₂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 = 00₂
1 = 01₂
2 = 10₂
3 = 11₂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] <= 10⁵
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.

Python

def count_set_bits(n):
    count = 0
    while n > 0:
        count += n & 1
        n >>= 1
    return count

def sum_of_values_at_indexes(nums, k):
    total_sum = 0
    for i in range(len(nums)):
        if count_set_bits(i) == k:
            total_sum += nums[i]
    return total_sum

nums = [5, 10, 1, 5, 2]
k = 1
print(sum_of_values_at_indexes(nums, k))

Java

public class SumOfIndices {
    public static int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }

    public static int sumOfValuesAtIndexes(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (countSetBits(i) == k) {
                sum += nums[i];
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {5, 10, 1, 5, 2};
        int k = 1;
        System.out.println(sumOfValuesAtIndexes(nums, k));
    }
}

C++

#include <iostream>
#include <vector>

int countSetBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int sumOfValuesAtIndexes(const std::vector<int>& nums, int k) {
    int sum = 0;
    for (size_t i = 0; i < nums.size(); ++i) {
        if (countSetBits(i) == k) {
            sum += nums[i];
        }
    }
    return sum;
}

int main() {
    std::vector<int> nums = {5, 10, 1, 5, 2};
    int k = 1;
    std::cout << sumOfValuesAtIndexes(nums, k) << std::endl;
    return 0;
}

JavaScript

function countSetBits(n) {
    let count = 0;
    while (n > 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

function sumOfValuesAtIndexes(nums, k) {
    let totalSum = 0;
    for (let i = 0; i < nums.length; i++) {
        if (countSetBits(i) === k) {
            totalSum += nums[i];
        }
    }
    return totalSum;
}

const nums = [5, 10, 1, 5, 2];
const k = 1;
console.log(sumOfValuesAtIndexes(nums, k));

#include <stdio.h>

int countSetBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int sumOfValuesAtIndexes(int nums[], int length, int k) {
    int sum = 0;
    for (int i = 0; i < length; i++) {
        if (countSetBits(i) == k) {
            sum += nums[i];
        }
    }
    return sum;
}

int main() {
    int nums[] = {5, 10, 1, 5, 2};
    int k = 1;
    int length = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", sumOfValuesAtIndexes(nums, length, k));
    return 0;
}

using System;

class Program
{
    static int CountSetBits(int n)
    {
        int count = 0;
        while (n > 0)
        {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }

    static int SumOfValuesAtIndexes(int[] nums, int k)
    {
        int sum = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            if (CountSetBits(i) == k)
            {
                sum += nums[i];
            }
        }
        return sum;
    }

    static void Main()
    {
        int[] nums = {5, 10, 1, 5, 2};
        int k = 1;
        Console.WriteLine(SumOfValuesAtIndexes(nums, k));
    }
}

In this Python solution, we utilize a function count_set_bits to determine the number of set bits in the binary representation of an index. We then iterate over each index, accumulating results based on whether the number of set bits matches k.

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.

Python

def sum_of_values_at_indexes(nums, k):
    total_sum = 0
    for i in range(len(nums)):
        if bin(i).count('1') == k:
            total_sum += nums[i]
    return total_sum

nums = [5, 10, 1, 5, 2]
k = 1
print(sum_of_values_at_indexes(nums, k))

Java

public class SumOfIndicesOptimized {
    public static int sumOfValuesAtIndexes(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (Integer.bitCount(i) == k) {
                sum += nums[i];
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {5, 10, 1, 5, 2};
        int k = 1;
        System.out.println(sumOfValuesAtIndexes(nums, k));
    }
}

JavaScript

function sumOfValuesAtIndexes(nums, k) {
    let totalSum = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i.toString(2).split('1').length - 1 === k) {
            totalSum += nums[i];
        }
    }
    return totalSum;
}

const nums = [5, 10, 1, 5, 2];
const k = 1;
console.log(sumOfValuesAtIndexes(nums, k));

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.

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

TypeScript

function sumIndicesWithKSetBits(nums: number[], k: number): number {
    let ans = 0;
    for (let i = 0; i < nums.length; ++i) {
        if (bitCount(i) === k) {
            ans += nums[i];
        }
    }
    return ans;
}

function bitCount(n: number): number {
    let count = 0;
    while (n) {
        n &= n - 1;
        count++;
    }
    return count;
}

func sumIndicesWithKSetBits(nums []int, k int) (ans int) {
	for i, x := range nums {
		if bits.OnesCount(uint(i)) == k {
			ans += x
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

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

Complexity analysis

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

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.

Sum of Values at Indices With K Set Bits solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Popcount Approach

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Sum of Values at Indices With K Set Bits solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Popcount Approach

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems