Minimum Operations to Reduce X to Zero (Medium) : Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Minimum Operations to Reduce X to Zero (Medium)” problem.
Problem explanation:
We were given an array, and we were tasked with reducing the elements present in the array to zero while minimizing the number of operations. Let me explain the problem:
Leet Code : longest common prefix string C++ ,java , Python Solution
In the example above, we have an array ‘nums‘ containing the elements [1, 1, 4, 2, 3], and we are given a target value X = 5. The goal is to find two possible solutions:
- One solution involves adding 1 + 1 + 3, which equals X. In this case, the number of elements to reduce to zero is 3.
- Another solution involves adding 2 + 3, which also equals X. Here, the number of elements to reduce to zero is 2.
For a clearer understanding of this example, please refer to Hand Written Example.
Method:Prefix Sum+Hashmap(Longest Sub Array Approach )
To solve the problem of “Minimum Operations to Reduce X to Zero,” the approach that comes to mind is to think about it in reverse. If you can find the length of the longest subarray with a sum equal to the total sum of the array minus X (where X is given to us), you will have the length of the subarray, and we can find a minimum number of elements to reduce X to zero by Subtracting the Length of Array to the length of the subarray.
minimum number of elements to reduce X to zero = Length of Array – length of the subarray
To implement this approach effectively, you can utilize the Prefix Sum and Hashmap approach.
You can view the Dry and Run of Example in the Handwritten Solution.
Steps: Prefix Sum and Hashmap approach
here are the steps broken down for solving the problem “LeetCode 1658. Minimum Operations to Reduce X to Zero” using the Prefix Sum and Hashmap approach:
- Start with the given array.
- Compute the Prefix Sum of the array. This is done by iterating through the array and at each index, storing the cumulative sum from the beginning of the array up to that index.
- Initialize a Hashmap to keep track of the sum and its corresponding index encountered during the Prefix Sum calculation.
- Calculate the target sum we want to achieve: (SUM of the entire array – X).
- Iterate through the Prefix Sum array:
a. At each step, check if the current sum minus the target sum exists in the Hashmap. If it does, this means we have found a subarray with the desired sum.
b. Update the length of the subarray by subtracting the index where we initially encountered the sum from the current index.
c. Keep track of the maximum subarray length encountered during the iteration. - After iterating through the entire Prefix Sum array, you will have the length of the longest subarray with a sum equal to (SUM of the array – X).
- To find the minimum number of elements to reduce X to zero, subtract the length of the longest subarray from the total length of the array.
- The result obtained in step 7 represents the minimum number of operations required to reduce X to zero.
These steps outline the approach to solving the problem effectively, considering the provided array, Prefix Sum, and Hashmap.
Time Complexity : O(N)
Codes: Prefix Sum + Hashmap (Longest Sum Sub Array Approach )
C++:Prefix Sum + Hashmap (Longest Sum Sub Array Approach )
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int n = nums.size();
int sum = 0;
unordered_map<int,int> mp; //<sum,pos>
for(int i=0;i<n;++i)
{
sum+=nums[i];
mp[sum] = i;
}
if(x>sum) //Sum out of range
return -1;
mp[0] = 0;
int longsubarray = 0;
sum-=x;
int val = 0;
for(int i=0;i<n;++i)
{
val += nums[i];
if(mp.count(val-sum))
{
if(val-sum==0)
longsubarray = max(longsubarray,i-mp[val-sum]+1);
else
longsubarray = max(longsubarray,i-mp[val-sum]);
}
}
return longsubarray==0?(sum==0?n:-1):n-longsubarray;
}
};Python:Prefix Sum + Hashmap (Longest Sum Sub Array Approach )
class Solution:
def minOperations(self, nums, x):
n = len(nums)
_sum = 0
mp = {0: 0} # <sum, pos>
for i in range(n):
_sum += nums[i]
mp[_sum] = i
if x > _sum: # Sum out of range
return -1
mp[0] = 0
longsubarray = 0
_sum -= x
val = 0
for i in range(n):
val += nums[i]
if val - _sum in mp:
if val - _sum == 0:
longsubarray = max(longsubarray, i - mp[val - _sum] + 1)
else:
longsubarray = max(longsubarray, i - mp[val - _sum])
return n - longsubarray if longsubarray != 0 else n if _sum == 0 else -1Java: Prefix Sum + Hashmap (Longest Sum Sub Array Approach )
import java.util.*;
class Solution {
public int minOperations(int[] nums, int x) {
int n = nums.length;
int sum = 0;
Map<Integer, Integer> mp = new HashMap<>(); // <sum, pos>
for (int i = 0; i < n; ++i) {
sum += nums[i];
mp.put(sum, i);
}
if (x > sum) { // Sum out of range
return -1;
}
mp.put(0, 0);
int longsubarray = 0;
sum -= x;
int val = 0;
for (int i = 0; i < n; ++i) {
val += nums[i];
if (mp.containsKey(val - sum)) {
if (val - sum == 0) {
longsubarray = Math.max(longsubarray, i - mp.get(val - sum) + 1);
} else {
longsubarray = Math.max(longsubarray, i - mp.get(val - sum));
}
}
}
return longsubarray == 0 ? (sum == 0 ? n : -1) : n - longsubarray;
}
}JavaScript: Prefix Sum + Hashmap (Longest Sum Sub Array Approach )
class Solution {
minOperations(nums, x) {
let n = nums.length;
let sum = 0;
let mp = new Map(); // <sum, pos>
for (let i = 0; i < n; ++i) {
sum += nums[i];
mp.set(sum, i);
}
if (x > sum) { // Sum out of range
return -1;
}
mp.set(0, 0);
let longsubarray = 0;
sum -= x;
let val = 0;
for (let i = 0; i < n; ++i) {
val += nums[i];
if (mp.has(val - sum)) {
if (val - sum === 0) {
longsubarray = Math.max(longsubarray, i - mp.get(val - sum) + 1);
} else {
longsubarray = Math.max(longsubarray, i - mp.get(val - sum));
}
}
}
return longsubarray === 0 ? (sum === 0 ? n : -1) : n - longsubarray;
}
}List of Some Important Leet Code Question :