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

Table of Contents

Meta Data
#

Difficulty: easy First Attempt: 2023-09-17

Submissions: Accepted (first try)

Approach
#

For each index i, count the 1s in bin(i) (Bit Manipulation) and add nums[i] when there are exactly k.

My Solution
#

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        return sum(x for i, x in enumerate(nums) if bin(i).count("1") == k)

Complexity
#

Time O(n log n), space O(1).

Mistakes to Avoid
#

Test the index, not nums[i].

Interview Explanation
#

For each index I count its set bits and add the value when the count is k. Time O(n log n).

LeetCode 136: Single Number

2022-08-16·1 min

LeetCode Easy Array Bit-Manipulation

LeetCode 136 note: x ^ x = 0 and x ^ 0 = x, so XOR everything; pairs cancel and the single number remains

LeetCode 1018: Binary Prefix Divisible By 5

2022-09-27·1 min

LeetCode Easy Array Bit-Manipulation

LeetCode 1018 note: each new bit turns the prefix into x = 2x + bit, so keep only x mod 5 and the number never grows

LeetCode 832: Flipping an Image

2022-09-15·2 mins

LeetCode Easy Array Two-Pointers Bit-Manipulation Matrix

LeetCode 832 note: reverse each row and invert its bits, which two pointers can do at once

LeetCode 645: Set Mismatch

2022-08-29·2 mins

LeetCode Easy Array Hash-Table Bit-Manipulation Sorting

LeetCode 645 note: use sums: missing = sum of 1..n - sum of the set, duplicate = array sum - sum of the set

LeetCode 1413: Minimum Value to Get Positive Step by Step Sum

2022-11-23·1 min

LeetCode Easy Array Prefix-Sum

LeetCode 1413 note: the start value plus every prefix sum must be at least 1, so it is max(1, 1 - minimum prefix sum)

LeetCode 1480: Running Sum of 1d Array

2022-11-23·1 min

LeetCode Easy Array Prefix-Sum

LeetCode 1480 note: the definition of a prefix sum, adding each element to the previous running total

Meta Data#

Approach#

My Solution#

Complexity#

Mistakes to Avoid#

Interview Explanation#

Related