Sum of Values at Indices With K Set Bits

EASY

Description

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

Approaches

Checkout 3 different approaches to solve Sum of Values at Indices With K Set Bits. Click on different approaches to view the approach and algorithm in detail.

Brute Force with String Conversion

This approach iterates through each index of the array. For each index, it converts the number to its binary string representation and then counts the occurrences of the character '1'. If this count matches k, the corresponding element from nums is added to the total sum.

Algorithm

Initialize a variable sum to 0.
Iterate with an index i from 0 to nums.size() - 1.
For each index i, convert it to a binary string using Integer.toBinaryString(i).
Initialize a setBitsCount to 0.
Iterate through each character of the binary string. If the character is '1', increment setBitsCount.
If the final setBitsCount is equal to k, add the value nums.get(i) to sum.
After the loop finishes, return the final sum.

This is a straightforward brute-force method. The core idea is to loop through every index from 0 to nums.size() - 1. In each iteration, we need to determine if the index has k set bits. We accomplish this by first converting the integer index to its binary string equivalent (e.g., 5 becomes "101"). Then, we iterate over this string, character by character, counting how many '1's we find. If this count equals the target k, we add the element at that index, nums.get(i), to our running total.

import java.util.List;

class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            String binaryString = Integer.toBinaryString(i);
            int setBitsCount = 0;
            for (char c : binaryString.toCharArray()) {
                if (c == '1') {
                    setBitsCount++;
                }
            }
            if (setBitsCount == k) {
                sum += nums.get(i);
            }
        }
        return sum;
    }
}

Complexity Analysis

Time Complexity: O(N * log N), where N is the length of the `nums` array. The outer loop runs N times. Inside the loop, converting an integer `i` to a binary string takes O(log i) time, and then iterating through the string to count bits also takes O(log i) time.Space Complexity: O(log N), where N is the length of the `nums` array. This space is required to store the binary string representation of the largest index, which has a length of O(log N).

Pros and Cons

Pros:

Easy to understand and implement for beginners.
The logic directly follows the problem statement.

Cons:

Inefficient due to the overhead of creating and iterating through strings for each number.
Higher space complexity compared to bit manipulation approaches.

Code Solutions

Checking out 3 solutions in different languages for Sum of Values at Indices With K Set Bits. Click on different languages to view the code.

class Solution {
public
  int sumIndicesWithKSetBits(List<Integer> nums, int k) {
    int ans = 0;
    for (int i = 0; i < nums.size(); i++) {
      if (Integer.bitCount(i) == k) {
        ans += nums.get(i);
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Sum of Values at Indices With K Set Bits

Patterns:

Bit Manipulation

Data Structures:

Array

Companies:

Accenture |