We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Values at Indices With K Set Bits

Number: 3093

Difficulty: Easy

Paid? No

Companies: Adobe, Accenture

Problem Description

Given an array of integers and an integer k, compute the sum of elements in the array where the index of each element has exactly k set bits in its binary representation.

Key Insights

  • The problem requires iterating through the array and checking the binary representation of each index.
  • Counting set bits in an index can be done by converting the index to its binary representation and counting '1's or by using bit manipulation techniques.
  • The solution is straightforward since the constraints are small (nums.length <= 1000).

Space and Time Complexity

Time Complexity: O(n * log(n)) where n is the length of the array (each index conversion and set bit counting takes O(log(n)) time).
Space Complexity: O(1) additional space.

Solution

We iterate over each index in the array and count the number of set bits in the index using a helper function or built-in functionality. Whenever an index has exactly k set bits, we add its corresponding value in the array to the running total. The approach leverages simple bit manipulation and iteration to efficiently compute the required sum.

Code Solutions

def sum_indices_with_k_set_bits(nums, k):
    total = 0
    # Iterate over each index and value in the array
    for i, num in enumerate(nums):
        # Convert the index to binary and count the number of '1's
        if bin(i).count('1') == k:
            total += num
    return total

# Example usage:
nums = [5, 10, 1, 5, 2]
k = 1
print(sum_indices_with_k_set_bits(nums, k))  # Expected output: 13
← Back to All Questions