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