# Sum of Values at Indices With K Set Bits
**Difficulty:** EASY
[External](https://leetcode.com/problems/sum-of-values-at-indices-with-k-set-bits)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-values-at-indices-with-k-set-bits
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture)
---
## 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 = 0002
1 = 0012
2 = 0102
3 = 0112
4 = 1002 
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 = 002
1 = 012
2 = 102
3 = 112
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] <= 105`
* `0 <= k <= 10`

# Approaches
## 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.
**Time:** 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:** 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:** 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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Brute Force with Bit Manipulation
This method improves upon the first by avoiding string conversion. It directly counts the set bits of each index using a bit manipulation trick known as Brian Kernighan's algorithm. This algorithm is efficient because it iterates only as many times as there are set bits. It works by repeatedly unsetting the rightmost set bit of a number (`n = n & (n - 1)`) until the number becomes zero, counting the number of operations.
**Time:** O(N * log N), where N is the length of `nums`. The outer loop runs N times. The inner bit-counting loop runs as many times as there are set bits in `i`, which is at most O(log i). While asymptotically the same as the string approach, it's significantly faster in practice. · **Space:** O(1), as it only uses a few variables for calculation, requiring no extra space that scales with the input size.
**Pros:** More efficient than string conversion as it uses fast, low-level bitwise operations.; Constant space complexity.
**Cons:** Still involves a sub-loop for each number, making it less performant than a single-instruction built-in function.
### Explanation
Instead of the costly process of converting numbers to strings, we can use bitwise operations for a more performant solution. Brian Kernighan's algorithm is a classic technique for counting set bits. The key insight is that for any number `n`, the operation `n & (n - 1)` unsets the least significant set bit (the rightmost '1'). By repeatedly applying this operation in a loop until `n` becomes 0, we can count exactly how many set bits were originally present. We apply this counting method to each index `i` and add `nums.get(i)` to the sum if the bit count equals `k`.

```java
import java.util.List;

class Solution {
    private int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            n &= (n - 1); // This clears the least significant set bit
            count++;
        }
        return count;
    }

    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (countSetBits(i) == k) {
                sum += nums.get(i);
            }
        }
        return sum;
    }
}
```
### Algorithm
- Initialize a variable `sum` to 0.
- Iterate with an index `i` from 0 to `nums.size() - 1`.
- For each index `i`, define a helper function or inline logic to count its set bits using Brian Kernighan's algorithm.
- To count bits for a number `n`:
  - Initialize `count = 0`.
  - While `n > 0`, repeatedly apply the operation `n = n & (n - 1)` and increment `count`.
- If the returned count is equal to `k`, add the value `nums.get(i)` to `sum`.
- After the loop, return `sum`.

## Optimized Approach Using Built-in Function
This is the most efficient and concise approach. Most programming languages provide a built-in function to count the number of set bits in an integer's binary representation. In Java, `Integer.bitCount()` can be used. This function is highly optimized and often maps to a single, fast machine instruction (like `popcnt` on modern CPUs), making the bit counting an effectively constant-time operation.
**Time:** O(N), where N is the length of the `nums` array. The loop runs N times, and `Integer.bitCount()` is effectively a constant time operation, O(1), as it operates on a fixed-size integer (32 bits). · **Space:** O(1), as no extra space proportional to the input size is required.
**Pros:** Most efficient in terms of time complexity.; Code is clean, concise, and easy to read.; Leverages platform-specific optimizations for maximum speed.
**Cons:** Relies on the availability of a specific built-in function in the programming language, which might not be present in all environments.
### Explanation
The optimal solution leverages the standard library's built-in capabilities. Java's `Integer.bitCount(int i)` method is specifically designed for this purpose. It returns the number of one-bits (also known as the population count) in the two's complement binary representation of an `int` value. This function is implemented with highly optimized, often hardware-level, instructions. By using this function, we can simplify our code and achieve the best possible performance. The overall algorithm remains the same: iterate through indices, but the check for `k` set bits becomes a single, efficient function call.

```java
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++) {
            if (Integer.bitCount(i) == k) {
                sum += nums.get(i);
            }
        }
        return sum;
    }
}
```
### Algorithm
- Initialize a variable `sum` to 0.
- Iterate with an index `i` from 0 to `nums.size() - 1`.
- Use the built-in function `Integer.bitCount(i)` to get the number of set bits for the index `i` in a single step.
- If the result of `Integer.bitCount(i)` is equal to `k`, add the value `nums.get(i)` to `sum`.
- After the loop finishes, return the final `sum`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int sumIndicesWithKSetBits(vector<int> &nums, int k) {
    int ans = 0;
    for (int i = 0; i < nums.size(); ++i) {
      if (__builtin_popcount(i) == k) {
        ans += nums[i];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int: return sum(
        x for i, x in enumerate(nums) if i . bit_count() == k)

```