Minimum Operations to Form Subsequence With Target Sum — LeetCode 2835 Python Solution

The problem

You are given a 0-indexed array nums consisting of non-negative powers of 2, and an integer target. In one operation, you must apply the following changes to the array: Choose any element of the array nums[i] such that nums[i] > 1.

Example

Input

nums = [1,2,8], target = 7

Output

1

Explanation

In the first operation, we choose element nums[2]. The array becomes equal to nums = [1,2,4,4].

Python solution

class Solution:
    def minOperations(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s < target:
            return -1
        cnt = [0] * 32
        for x in nums:
            for i in range(32):
                if x >> i & 1:
                    cnt[i] += 1
        i = j = 0
        ans = 0
        while 1:
            while i < 32 and (target >> i & 1) == 0:
                i += 1
            if i == 32:
                break
            while j < i:
                cnt[j + 1] += cnt[j] // 2
                cnt[j] %= 2
                j += 1
            while cnt[j] == 0:
                cnt[j] = 1
                j += 1
            ans += j - i
            cnt[j] -= 1
            j = i
            i += 1
        return ans

Complexity

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2835. Minimum Operations to Form Subsequence With Target Sum is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems