algoadvance

Leetcode 2859. Sum of Values at Indices With K Set Bits

Problem Statement

LeetCode Problem 2859: Sum of Values at Indices With K Set Bits

Description: Given a 0-indexed integer array nums and an integer k, return the sum of the elements of nums at indices having exactly k set bits in their binary representation.

Example:

Input: nums = [1,2,3,4], k = 1
Output: 6
Explanation: The indices with one set bit are 01 and 10, respectively indices 1 and 2.

Clarifying Questions

  1. Q: What are the constraints on the size of the input array and the values in the array?
    • A: There is no specified constraint in the problem description, so we should assume typical constraint values like 1 <= nums.length <= 10^5 and integer values within standard ranges.
  2. Q: Can k be greater than the number of bits in the indices?
    • A: Yes, but in such cases, the result should naturally be 0 as no index will have more set bits than its bit-length.
  3. Q: How do we determine what k set bits are?
    • A: The number of set bits in binary representation of an index can be determined using bit manipulation or built-in functions.

Code

#include <iostream>
#include <vector>
using namespace std;

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

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3, 4};
    int k = 1;
    int result = sol.sumIndicesWithKSetBits(nums, k);
    cout << "Sum of values at indices with " << k << " set bits is: " << result << endl;
    return 0;
}

Strategy

  1. Count Set Bits: Use the built-in GCC function __builtin_popcount to count the number of set bits in the index.
  2. Sum Matching Indices: Iterate through the array and sum the values where the index has exactly k set bits.

Time Complexity

This method is efficient and leverages built-in functions for simplicity and speed.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI