2702. Minimum Operations to Make Numbers Non-positive
Problem Description
In this problem, we have an array of non-negative integers called nums
and two positive integers x
and y
. We are allowed to perform operations on the array with the aim of reducing all the elements to zero or less. In each operation, we can choose an index i
and decrease the element at that index nums[i]
by x
and simultaneously decrease all other elements by y
. The task is to find and return the minimum number of such operations required to achieve the target condition where every element of the array is less than or equal to zero.
Intuition
To arrive at the solution, we need to recognize that decreasing all elements in the array besides the chosen index i
by y
in each operation will set a pace for how quickly the array can reach <= 0
. This pace is constrained by the smallest element since it will hit zero first due to the decrement by y
in each operation. The chosen element decremented by x
will go down faster, so we want to figure out how often we need to 'hit' an element with the x
decrement to bring it down to zero along with the rest of the elements.
A sound approach here is to perform a binary search on the number of operations t
we would need since the answer will range between 0
and the maximum element in nums
. For any guess t
, we calculate if it's possible to bring all elements to less than or equal to zero within t
operations. To do this, for each v
in nums, we check if v > t * y
, meaning the decay by y
alone wouldn't be enough. If so, we need additional decrements of x - y
to bring it down, which we calculate using ceil((v - t * y) / (x - y))
. If the sum of additional decrements for all elements is less than or equal to t
, we've found a viable candidate for the number of operations, and we can try to lower our guess. If not, we need to increase it. The first t
that satisfies the condition for all elements in nums
will be our answer.
This binary search loop continues until we narrow down the number of operations needed to a single value, which is then returned as the minimum number of operations required.
Learn more about Binary Search patterns.
Solution Approach
The solution uses a binary search algorithm to efficiently narrow down the minimum number of operations. The reasoning behind using binary search is that we're dealing with a monotonic condition: if we can bring down all elements to zero or less in t
operations, we can also do it in t+1
, t+2
, etc. So, we try to find the smallest t
for which the condition holds true.
Here are the steps of the implemented solution:
-
Define an inner function
check(t: int) -> bool
that will verify if we can achieve the target witht
operations. It performs the following steps:- Initialize a counter variable
cnt
to 0. - Loop through each element
v
innums
. - Within the loop, check if
v
is greater thant * y
. If it is, calculate the extra decrements needed by subtractingt * y
fromv
, and then dividing the rest byx - y
usingceil
. This ensures that we take into account the integer division rounding. - Increment
cnt
by the number computed. This represents the number of timesx
decrement should be applied to each element. - If the sum of decrements
cnt
is less than or equal tot
, returnTrue
; otherwise returnFalse
.
- Initialize a counter variable
-
Conduct the binary search between
l = 0
andr = max(nums)
, as the answer is in this range:- While
l < r
, calculatemid
which is the midpoint ofl
andr
. - Call
check(mid)
to verify ift = mid
is a viable number of operations. - If
check(mid)
returnsTrue
, we can potentially reduce the number of operations, so setr
tomid
. - Else, if
check(mid)
returnsFalse
, we need more operations to reach the target, so setl
tomid + 1
.
- While
-
The loop ends when
l
is equal tor
, meaning we've found the smallest possiblet
wherecheck(t)
isTrue
. Returnl
as the minimum number of operations required.
The reason we use (l + r) >> 1
to calculate the midpoint is that it is equivalent to (l + r) / 2
, but faster in terms of execution as it is a bit shift operation.
The time complexity of this solution is O(nlog(maxElement))
, where n
is the number of elements in nums
. The log factor comes from the binary search, and for each step of the search, we iterate through the array once to check if the current t
is viable. The space complexity is O(1)
since we only use a few variables for the binary search and the checks.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have an array nums = [3, 19, 10]
and the integers x = 7
and y = 5
.
The target condition is to reduce all elements to zero or less. According to the solution approach, we can perform a binary search to find the minimum number of operations, t
.
Step by step, here's how the solution works with this example:
-
We estimate the bounds [
l
,r
] for the binary search. The upper boundr
can be the maximum element innums
, which is 19. We start withl = 0
. -
We define our
check
function, which will determine if a given number of operationst
is sufficient to reduce all the elements innums
to zero or less. -
We begin the binary search. With
l = 0
andr = 19
, we calculate the midpointmid
to check.mid
is(0 + 19) >> 1 = 9
. -
We call
check(9)
to verify ift = 9
is a viable number of operations:- For
nums[0] = 3
, since3 <= 9 * 5
, we don't need any extra decrements becausey
decrements alone will bring it down to zero. - For
nums[1] = 19
, since19 > 9 * 5
, we do the mathceil((19 - 9 * 5) / (7 - 5)) = ceil((19 - 45) / 2) = ceil(-26 / 2) = 0
. So no extra decrements are needed. - For
nums[2] = 10
, since10 > 9 * 5
, we doceil((10 - 9 * 5) / (7 - 5)) = ceil((10 - 45) / 2) = ceil(-35 / 2) = 0
. - Sum of extra decrements needed is
0
which is<= 9
, socheck(9)
returnsTrue
.
- For
-
Since
check(9)
returnsTrue
, we can potentially reduce the number of operations. Now our new upper boundr
is set to our currentmid
, which is 9. We repeat the binary search with new boundsl = 0
andr = 9
and find the midpoint again. -
After some iterations, we might find that lower values of
t
also pass the check function (in this example,t = 1
could also work since none of the elements need extra decrements). Binary search will continue untill == r
. -
Once we find the smallest
t
such thatcheck(t)
isTrue
, that will be our answer for the minimum number of operations required.
This detailed example walkthrough shows us how the binary search can efficiently find the minimum number of operations to reduce all array elements to zero or less. In this instance, given x
and y
are much larger than the array elements, even one operation is sufficientāhence the answer is t = 1
.
Solution Implementation
1from math import ceil
2from typing import List
3
4class Solution:
5 def minOperations(self, nums: List[int], x: int, y: int) -> int:
6 # Helper function to check if the operation can be completed with 't' operations.
7 def is_possible_with_t_operations(t: int) -> bool:
8 # Initialize count of operations.
9 operations = 0
10 # Iterate through each number in the list.
11 for value in nums:
12 # If the value is greater than 't' times 'y', operations are needed.
13 if value > t * y:
14 # Calculate the number of operations needed for the current value, and add to the total.
15 operations += ceil((value - t * y) / (x - y))
16 # Return True if the counted operations are less than or equal to 't', else return False.
17 return operations <= t
18
19 # Initialize left and right pointers for the binary search.
20 left, right = 0, max(nums)
21 # Perform binary search to find the minimum number of operations required.
22 while left < right:
23 # Get the middle value between left and right.
24 mid = (left + right) >> 1 # Using bitwise shift to divide by 2.
25 # If the operation is possible with 'mid' operations, move the right boundary to 'mid'.
26 if is_possible_with_t_operations(mid):
27 right = mid
28 # Otherwise, move the left boundary past 'mid'.
29 else:
30 left = mid + 1
31 # The left pointer will now point to the minimum number of operations needed.
32 return left
33
1class Solution {
2 private int[] numbers;
3 private int x;
4 private int y;
5
6 // This method aims to find the minimum number of operations required.
7 // It uses a binary search approach to find the minimum 't'.
8 public int minOperations(int[] numbers, int x, int y) {
9 this.numbers = numbers;
10 this.x = x;
11 this.y = y;
12
13 // Initializing search range for 't'.
14 int left = 0;
15 int right = 0;
16
17 // Find the largest number in the array to set the upper bound for 't'.
18 for (int value : numbers) {
19 right = Math.max(right, value);
20 }
21
22 // Perform binary search to find the minimum 't'.
23 while (left < right) {
24 int mid = (left + right) >>> 1; // Calculate the mid value for 't'.
25 if (isFeasible(mid)) {
26 right = mid; // Found new possible minimum, adjust right bound.
27 } else {
28 left = mid + 1; // Target not feasible, adjust left bound.
29 }
30 }
31 return left; // Return the minimum number of operations required.
32 }
33
34 // This helper method checks if it's possible to achieve the goal
35 // with 't' operations, where each operation reduces a number in the array by x until it's no smaller than t * y.
36 private boolean isFeasible(int target) {
37 long count = 0; // Initialize the count of operations.
38
39 // Check each number in the array to see if operations are needed.
40 for (int value : numbers) {
41 if (value > (long) target * y) {
42 // Calculate operations required for current value and add to count.
43 count += (value - (long) target * y + x - y - 1) / (x - y);
44 }
45 }
46 // Check if the count of operations is less than or equal to target to meet the constraint.
47 return count <= target;
48 }
49}
50
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 int minOperations(std::vector<int>& nums, int increment, int decrement) {
7 // Using binary search to find the minimum number of operations
8 // Initialize the left (l) and right (r) boundaries for binary search
9 int left = 0, right = *std::max_element(nums.begin(), nums.end());
10
11 // Lambda to check if a given number of operations (ops) is sufficient
12 auto isSufficient = [&](int ops) {
13 long long requiredOps = 0;
14 for (int value : nums) {
15 if (value > 1LL * ops * decrement) {
16 // Calculate additional operations needed for this value
17 requiredOps += (value - 1LL * ops * decrement + increment - decrement - 1) / (increment - decrement);
18 }
19 }
20 return requiredOps <= ops; // Return true if the total required operations are within the limit
21 };
22
23 // Binary search to find the minimum number of operations required
24 while (left < right) {
25 int mid = (left + right) >> 1; // Calculate the mid-point
26 if (isSufficient(mid)) {
27 right = mid; // If mid operations are sufficient, we look for a potential smaller number
28 } else {
29 left = mid + 1; // If mid operations are not sufficient, we need more operations
30 }
31 }
32
33 return left; // Once the search is narrowed down to a single element, left will be the minimum number of operations
34 }
35};
36
1function minOperations(nums: number[], x: number, y: number): number {
2 // Initialize pointers l and r for the binary search
3 let left = 0;
4 let right = Math.max(...nums);
5
6 // Define a check function that will return true if the operation is possible within t actions
7 const check = (threshold: number): boolean => {
8 // Initialize a counter for the number of operations performed
9 let operations = 0;
10
11 // Iterate over each value in the array
12 for (const value of nums) {
13 // If the value is greater than the threshold times y, calculate the necessary operations
14 if (value > threshold * y) {
15 // Add the ceil of the division to the operations' counter
16 operations += Math.ceil((value - threshold * y) / (x - y));
17 }
18 }
19
20 // Return true if the total operations are less than or equal to the threshold
21 return operations <= threshold;
22 };
23
24 // Use binary search to find the minimum number of operations to reach a certain state
25 while (left < right) {
26 // Find the mid-point of the current search range
27 const mid = (left + right) >> 1;
28
29 // If the current mid value satisfies the condition, adjust the right pointer
30 if (check(mid)) {
31 right = mid;
32 } else {
33 // Otherwise, adjust the left pointer
34 left = mid + 1;
35 }
36 }
37
38 // Return the minimum number of operations after binary search completes
39 return left;
40}
41
Time and Space Complexity
The given code snippet is implementing a binary search algorithm to find the minimum number of operations needed to reduce certain elements in the array nums
so that no element is greater than t * y
. To determine if a given target t
is feasible, the check
function is employed, which computes the number of operations needed for each element in nums
. If the element is greater than t * y
, the number of operations to reduce it is added to cnt
.
The check
function is called with a time complexity of O(n)
where n
is the number of elements in nums
. This is because it iteratively checks each element once.
The binary search runs from 0 to the maximum value in nums
. The time complexity for binary search is O(log m)
, where m
is the range within which the binary search operates. Here m
corresponds to the maximum value in nums
.
The overall time complexity of the code is therefore O(n log m)
, since the binary search is the outer loop and the check
function is called within each iteration of this binary search.
As for the space complexity, the space used is constant and does not depend on the input size, besides the input array itself. No additional data structures that grow with input size are created. Thus, the space complexity is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!