Sum of Values at Indices With K Set Bits

#14 Most AskedEasy

Sum of Values at Indices With K Set Bits #14 Most Asked

Easy

Accenture

1 view

Topics:

ArraysBit Manipulation

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value for an element in the input array?
What is the maximum value of 'k'? Is 'k' guaranteed to be non-negative?
Can the input array be empty or null?
How should I handle the case where no indices have exactly k set bits?
Is 'k' referring to the number of bits equal to 1 in the binary representation of the index?

Brute Force Solution

Approach

We need to find numbers in a list whose position, when written in a special way, has a specific number of ones. The brute force way means checking every single number in the list one by one.

Here's how the algorithm would work step-by-step:

Take the first number in the list.
Figure out the position of this number within the list (first, second, third, and so on).
Convert this position into a binary representation (a sequence of zeros and ones).
Count how many ones are in this binary representation.
If the number of ones matches our target, then add the number from the list to a running total.
Repeat this process for every number in the list.
The final running total is the answer.

Code Implementation

def sum_of_values_with_k_set_bits_brute_force(numbers, k_set_bits):
    running_total = 0

    for index in range(len(numbers)):
        # The index needs to be in binary
        binary_representation = bin(index)[2:]

        # Count the number of set bits (1s) in the binary representation
        number_of_set_bits = binary_representation.count('1')

        # Accumulate the value only if the number of set bits matches
        if number_of_set_bits == k_set_bits:
            running_total += numbers[index]

    return running_total

Big(O) Analysis

Time Complexity

O(n*log(n)) – The algorithm iterates through each of the n elements in the input array (nums). For each element, it converts the index to its binary representation, which takes O(log(n)) time, where n is the length of the nums array, because the index will be bounded by the size of the array. The number of bits to represent a number grows logarithmically. Then it counts the set bits in the binary representation. This count also takes O(log(n)) time. Thus, the overall time complexity is O(n*log(n)).

Space Complexity

O(1) – The algorithm iterates through the input list, calculating the binary representation of the index and counting set bits. It only uses a few constant space variables to store the running total, the current index, and potentially temporary variables during the bit counting process. No auxiliary data structures dependent on the input size are created; the space needed remains constant regardless of the input list's size (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The key is to efficiently count how many '1's are in the binary representation of each position. Then, if the count matches the target number, add the value at that position to our total.

Here's how the algorithm would work step-by-step:

Go through each position in the list one by one.
For each position, find its binary representation.
Count how many '1's are in the binary form of that position number.
If the number of '1's is exactly the number we're looking for, then grab the number stored at that position.
Add that grabbed number to a running total.
After going through all positions, the running total will be the answer.

Code Implementation

def sum_of_values_at_indices_with_k_set_bits(numbers, k_set_bits):
    total_sum = 0

    for index, number in enumerate(numbers):
        # Convert the index to its binary representation.
        binary_representation = bin(index)[2:]

        # Count the number of set bits (1s) in the binary representation.
        number_of_set_bits = binary_representation.count('1')

        # Check if the number of set bits is equal to k.
        if number_of_set_bits == k_set_bits:
            # Accumulate sum only if set bit count matches
            total_sum += number

    return total_sum

Big(O) Analysis

Time Complexity

O(n * log(n)) – The algorithm iterates through each of the n elements in the input array nums. For each index i (from 0 to n-1), we compute the number of set bits in its binary representation. Computing the number of set bits for an index i can take up to log(i) time in the worst case (where i is close to n), since we need to examine the bits in the binary representation of i. Thus, in the worst case the bit counting operation for a given element takes O(log n) time. Therefore, the overall time complexity is O(n * log(n)).

Space Complexity

O(1) – The provided algorithm iterates through the input list, calculating the number of set bits for each index. While it implicitly computes the binary representation, it doesn't explicitly store it. The only extra memory used is for a few integer variables: the index itself, the count of set bits, and the running total. The amount of extra space used does not depend on the size of the input list; therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as there are no elements to sum.
k is 0	Sum all elements in the array, as all indices will have 0 set bits.
k is larger than the maximum possible number of bits in the index	Return 0, as no index can have more set bits than its maximum possible bit representation.
Array with only one element	Calculate the number of set bits in index 0 and return the element if it equals k, otherwise return 0.
Large array size causing potential integer overflow when summing	Use a data type with a larger range (e.g., long) to store the sum to prevent overflow.
Indices with leading zeros in their binary representation	The bit counting logic should correctly handle leading zeros, so this is not a special case.
All indices have k set bits	The solution should correctly sum all elements in the array in this scenario.
No indices have k set bits	The solution should return 0.

Null or empty input array

How to Handle:

Return 0 immediately, as there are no elements to sum.

k is 0

How to Handle:

Sum all elements in the array, as all indices will have 0 set bits.

k is larger than the maximum possible number of bits in the index

How to Handle:

Return 0, as no index can have more set bits than its maximum possible bit representation.

Array with only one element

How to Handle:

Calculate the number of set bits in index 0 and return the element if it equals k, otherwise return 0.

Large array size causing potential integer overflow when summing

How to Handle:

Use a data type with a larger range (e.g., long) to store the sum to prevent overflow.

Indices with leading zeros in their binary representation

How to Handle:

The bit counting logic should correctly handle leading zeros, so this is not a special case.

All indices have k set bits

How to Handle:

The solution should correctly sum all elements in the array in this scenario.

No indices have k set bits

How to Handle:

The solution should return 0.