Sum of Values at Indices With K Set Bits

Difficulty: Easy | Acceptance: 86.10% | Paid: No Topics: Array, Bit Manipulation

You are given a 0-indexed integer array nums and an integer k.

Return the sum of all nums[i] where the index i has exactly k set bits in its binary representation.

A set bit is a bit that is 1.

• Examples
• Constraints
• Iterative Bit Counting
• Built-in Bit Count Functions
• Brian Kernighan’s Algorithm

Examples

Example 1

Input: nums = [5,2,3,4], k = 1
Output: 5
Explanation:
Index 0: binary 00, has 0 set bits
Index 1: binary 01, has 1 set bit
Index 2: binary 10, has 1 set bit
Index 3: binary 11, has 2 set bits
So we sum nums[1] + nums[2] = 2 + 3 = 5

Example 2

Input: nums = [1,2,3,4,5], k = 2
Output: 4
Explanation:
Index 0: binary 000, has 0 set bits
Index 1: binary 001, has 1 set bit
Index 2: binary 010, has 1 set bit
Index 3: binary 011, has 2 set bits
Index 4: binary 100, has 1 set bit
So we sum nums[3] = 4

Constraints

1 <= nums.length <= 1000
0 <= nums[i] <= 10⁵
0 <= k <= 10

Iterative Bit Counting

Intuition For each index, count the number of set bits by checking each bit position and summing the values at indices with exactly k set bits.

Steps

• Iterate through each index of the array
• For each index, count set bits by repeatedly checking the least significant bit and right-shifting
• If the count equals k, add the value at that index to the total sum
• Return the total sum

from typing import List

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        def count_set_bits(n):
            count = 0
            while n:
                count += n & 1
                n >>= 1
            return count
        
        total = 0
        for i in range(len(nums)):
            if count_set_bits(i) == k:
                total += nums[i]
        return total

Complexity

• Time: O(n × log(max_index)) where n is the length of nums
• Space: O(1)
• Notes: Simple and straightforward approach, but may not be the most efficient for bit counting

Built-in Bit Count Functions

Intuition Leverage language-specific built-in functions to count set bits efficiently, then sum values at matching indices.

Steps

• Iterate through each index of the array
• Use the built-in bit count function to count set bits in the index
• If the count equals k, add the value at that index to the total sum
• Return the total sum

from typing import List

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        total = 0
        for i in range(len(nums)):
            if bin(i).count('1') == k:
                total += nums[i]
        return total

Complexity

• Time: O(n × log(max_index)) where n is the length of nums
• Space: O(1)
• Notes: Most concise and idiomatic approach, uses optimized built-in functions

Brian Kernighan’s Algorithm

Intuition Use Brian Kernighan’s algorithm to efficiently count set bits by repeatedly clearing the least significant set bit.

Steps

• Iterate through each index of the array
• For each index, count set bits using Brian Kernighan’s algorithm (n & (n-1) clears the least significant set bit)
• If the count equals k, add the value at that index to the total sum
• Return the total sum

from typing import List

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        def count_set_bits(n):
            count = 0
            while n:
                n &= n - 1
                count += 1
            return count
        
        total = 0
        for i in range(len(nums)):
            if count_set_bits(i) == k:
                total += nums[i]
        return total

Complexity

• Time: O(n × s) where n is the length of nums and s is the number of set bits in each index
• Space: O(1)
• Notes: More efficient when numbers have few set bits, as it only iterates through set bits