[Python3] DP + Binary Search
Intuition\n Describe your first thoughts on how to solve this problem. \nAt time t total sum without reduction is sum(nums1) + t * sum(nums2). \nWe need to prov
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAt time `t` total sum without reduction is `sum(nums1) + t * sum(nums2)`. \nWe need to provide such array of indices `[i_1 ... i_t]` that at time `t` we will remove number at index `i_t`. \nSearching for it manually for each `t` value will take in the worst case $$O(N^t)$$. \nSo, dynamic programming approach are used to find best possible reduction for each value from `1` to `N` (where `N` is length of array `nums1`). \n\nBinary search of minimal `t` value in the end helps to improve solution even further.\n\n\n# Complexity\n- Time complexity: $$O(N^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n        s1, s2 = sum(nums1), sum(nums2)\n        if s1 <= x:\n            return 0\n\n        dp = [0] * (len(nums1) + 1)  # best posssible reduction at time t\n        for add, base in sorted([(nums2[i], nums1[i]) for i in range(len(nums1))]):\n            for t in range(len(nums1) - 1, - 1, - 1):\n                dp[t + 1] = max(dp[t + 1], dp[t] + (t + 1) * add + base)\n\n        l, r = 1, len(nums1)\n        is_possible = lambda t: s2 * t + s1 - dp[t] <= x\n        while l < r:\n            m = (l + r) // 2\n            if is_possible(m):\n                r = m\n            else:\n                l = m + 1\n        return l if is_possible(l) else - 1\n```
['Binary Search', 'Dynamic Programming', 'Python3']