1658. Minimum Operations to Reduce X to Zero

Python

DFS with Prefix/Suffix Sum

(Timelimit Exceed)

from functools import cache
from math import inf

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n = len(nums)
        prefix_sum = [0, nums[0]]
        suffix_sum = [0, nums[-1]]

        for i in range(1, n):
            prefix_sum.append(prefix_sum[i] + nums[i])
            suffix_sum.append(suffix_sum[i] + nums[len(nums)-i-1])

        @cache
        def dfs(pre_i, suf_i):
            if pre_i == n or suf_i == n:
                return inf

            current_total = prefix_sum[pre_i] + suffix_sum[suf_i]

            if current_total > x:
                return inf

            if current_total == x:
                print("HIT", pre_i, suf_i)
                return pre_i + suf_i

            left_steps = dfs(pre_i+1, suf_i)
            right_steps = dfs(pre_i, suf_i+1)
            print(pre_i, suf_i, left_steps, right_steps)
            return min(left_steps, right_steps)

        steps = dfs(0, 0)
        return -1 if steps == inf else steps

Prefix Sum with Binary Search

from functools import cache
from math import inf

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n = len(nums)

        prefix_sum = [0, nums[0]]
        suffix_sum = [0, nums[-1]]
        for i in range(1, n):
            prefix_sum.append(prefix_sum[i] + nums[i])
            suffix_sum.append(suffix_sum[i] + nums[len(nums)-i-1])

        # print(prefix_sum, suffix_sum)

        if prefix_sum[-1] < x:
            # sum(nums) less than x, which is not possible to find ans
            return -1

        steps = inf
        for pre_step in range(n+1):
            pre = prefix_sum[pre_step]
            suf_step = self._bsearch(suffix_sum, x-pre)
            # print(pre_step, suf_step)
            if suf_step != -1:
                steps = min(steps, pre_step+suf_step)

        return -1 if steps == inf else steps

    @staticmethod
    def _bsearch(arr, target):
        left, right = 0, len(arr)-1

        while left <= right:
            pivot = (left + right) >> 1

            value = arr[pivot]
            if value == target:
                return pivot
            elif value < target:
                left = pivot + 1
            else:
                right = pivot - 1

        return -1