2809. Minimum Time to Make Array Sum At Most x LeetCode Solution
In this guide, you will get 2809. Minimum Time to Make Array Sum At Most x LeetCode Solution with the best time and space complexity. The solution to Minimum Time to Make Array Sum At Most x problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Time to Make Array Sum At Most x
You are given two 0-indexed integer arrays nums1 and nums2 of equal length. Every second, for all indices 0 <= i < nums1.length, value of nums1[i] is incremented by nums2[i]. After this is done, you can do the following operation:
Choose an index 0 <= i < nums1.length and make nums1[i] = 0.
You are also given an integer x.
Return the minimum time in which you can make the sum of all elements of nums1 to be less than or equal to x, or -1 if this is not possible.
Example 1:
Input: nums1 = [1,2,3], nums2 = [1,2,3], x = 4
Output: 3
Explanation:
For the 1st second, we apply the operation on i = 0. Therefore nums1 = [0,2+2,3+3] = [0,4,6].
For the 2nd second, we apply the operation on i = 1. Therefore nums1 = [0+1,0,6+3] = [1,0,9].
For the 3rd second, we apply the operation on i = 2. Therefore nums1 = [1+1,0+2,0] = [2,2,0].
Now sum of nums1 = 4. It can be shown that these operations are optimal, so we return 3.
Input: nums1 = [1,2,3], nums2 = [3,3,3], x = 4
Output: -1
Explanation: It can be shown that the sum of nums1 will always be greater than x, no matter which operations are performed.
2809. Minimum Time to Make Array Sum At Most x LeetCode Solution in C++
class Solution {
public:
int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {
const int n = nums1.size();
const int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
const int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
// dp[i][j] := the maximum reduced value if we do j operations on the first
// i numbers
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
vector<pair<int, int>> sortedNums;
for (int i = 0; i < n; ++i)
sortedNums.emplace_back(nums2[i], nums1[i]);
ranges::sort(sortedNums);
for (int i = 1; i <= n; ++i) {
const auto [num2, num1] = sortedNums[i - 1];
for (int j = 1; j <= i; ++j)
dp[i][j] = max(
// the maximum reduced value if we do j operations on the first
// i - 1 numbers
dp[i - 1][j],
// the maximum reduced value if we do j - 1 operations on the first
// i - 1 numbers + making the i-th number of `nums1` to 0 at the
// j-th operation
dp[i - 1][j - 1] + num2 * j + num1);
}
for (int op = 0; op <= n; ++op)
if (sum1 + sum2 * op - dp[n][op] <= x)
return op;
return -1;
}
}; /* code provided by PROGIEZ */
2809. Minimum Time to Make Array Sum At Most x LeetCode Solution in Java
class Solution {
public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
final int n = nums1.size();
final int sum1 = nums1.stream().mapToInt(Integer::intValue).sum();
final int sum2 = nums2.stream().mapToInt(Integer::intValue).sum();
// dp[i][j] := the maximum reduced value if we do j operations on the first
// i numbers
int[][] dp = new int[n + 1][n + 1];
List<Pair<Integer, Integer>> sortedNums = new ArrayList<>();
for (int i = 0; i < n; ++i)
sortedNums.add(new Pair<>(nums2.get(i), nums1.get(i)));
sortedNums.sort(Comparator.comparingInt(a -> a.getKey()));
for (int i = 1; i <= n; ++i) {
final int num2 = sortedNums.get(i - 1).getKey();
final int num1 = sortedNums.get(i - 1).getValue();
for (int j = 1; j <= i; ++j)
dp[i][j] = Math.max(
// the maximum reduced value if we do j ops on the first i - 1 nums
dp[i - 1][j],
// the maximum reduced value if we do j - 1 ops on the first i - 1
// nums + making i-th num of nums1 to 0 at j-th operation
dp[i - 1][j - 1] + num2 * j + num1);
}
for (int op = 0; op <= n; ++op)
if (sum1 + sum2 * op - dp[n][op] <= x)
return op;
return -1;
}
} // code provided by PROGIEZ
2809. Minimum Time to Make Array Sum At Most x LeetCode Solution in Python
class Solution:
def minimumTime(self, nums1: list[int], nums2: list[int], x: int) -> int:
n = len(nums1)
# dp[i][j] := the maximum reduced value if we do j operations on the first
# i numbers
dp = [[0] * (n + 1) for _ in range(n + 1)]
sum1 = sum(nums1)
sum2 = sum(nums2)
for i, (num2, num1) in enumerate(sorted(zip(nums2, nums1)), 1):
for j in range(1, i + 1):
dp[i][j] = max(
# the maximum reduced value if we do j operations on the first
# i - 1 numbers
dp[i - 1][j],
# the maximum reduced value if we do j - 1 operations on the first
# i - 1 numbers + making the i-th number of `nums1` to 0 at the
# j-th operation
dp[i - 1][j - 1] + num2 * j + num1
)
for op in range(n + 1):
if sum1 + sum2 * op - dp[n][op] <= x:
return op
return -1 # code by PROGIEZ
