Given an integer array of nums[] and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations, the task is to return the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return -1.
Examples:
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.Input: nums = [5,6,7,8,9], x = 4
Output: -1
Explanation: There is no way to make x to zero.
Approach: To solve the problem follow the below idea:
To make x to zero in minimum moves, Rephrasing this statement makes it possible to find the maximum subarray which has a sum equal to (totalSum-x).
Here’s an explanation of the approach used in this code:
- Calculate the total sum of all elements in the nums vector and store it in the totsum variable.
- Check if totsum is equal to x. If it is, return the size of the nums vector because the sum is already equal to x.
- Calculate the difference between totsum and x and store it in the totsum variable. This represents the target sum we want to achieve by removing elements from the vector.
- Initialize two pointers, s, and e, set to 0. These pointers represent the start and end of the current subarray we are considering.
- Initialize variables sum and ans to 0. The sum variable will keep track of the sum of the current subarray, and ans will store the maximum length of a subarray with a sum equal to totsum.
- Use a while loop with the e pointer to iterate through the elements of the nums vector.
- Add the element at index e to the sum.
- Use another while loop with the s pointer to adjust the subarray by removing elements from the beginning until sum is less than or equal to totsum.
- Check if sum is equal to totsum. If it is, update ans with the maximum length of the subarray found so far (e – s + 1).
- Increment the e pointer to consider the next element in the array.
- Finally, return the result: if ans is still 0, return -1 (indicating that it’s not possible to achieve the sum x), otherwise, return nums.size() – ans, which represents the minimum number of operations needed to achieve the desired sum.
Below is the implementation of the above approach:
C++
// C++ Code for the above approach:#include <bits/stdc++.h>using namespace std;class Solution {public: int minOperations(vector<int>& nums, int x) { int n = nums.size(); int totalS = 0; // Calculate the total sum of the // elements in the vector 'nums' for (int i = 0; i < n; i++) { totalS += nums[i]; } // If the total sum is equal to 'x', // no operations are needed if (totalS == x) { return n; } // Calculate the difference between // the total sum and 'x' totalS = totalS - x; int i = 0; int j = 0; int sum = 0; int ans = 0; // Sliding window approach to find // the minimum operations while (j < n) { sum += nums[j]; // If the current sum is greater // than the target difference, move // the window's left end (i) to // reduce the sum while (i < j && sum > totalS) { sum -= nums[i]; i++; } // If the current sum equals the // target difference, update the // answer with the maximum // window size if (sum == totalS) { ans = max(ans, j - i + 1); } j++; } // If 'ans' is still 0, it means no // subarray with the target sum was found return ans == 0 ? -1 : n - ans; }};// Drivers codeint main(){ Solution solution; vector<int> nums = { 1, 1, 4, 2, 3 }; int x = 5; int result = solution.minOperations(nums, x); if (result == -1) { cout << "No solution found." << endl; } else { cout << "Minimum operations required: " << result << endl; } return 0;} |
Java
// Java code for the above approachimport java.util.*;public class Solution { public int minOperations(int[] nums, int x) { int n = nums.length; int totalSum = 0; // Calculate the total sum of the elements in the // array 'nums' for (int i = 0; i < n; i++) { totalSum += nums[i]; } // If the total sum is equal to 'x', no operations // are needed if (totalSum == x) { return n; } // Calculate the difference between the total sum // and 'x' totalSum = totalSum - x; int i = 0; int j = 0; int sum = 0; int ans = 0; // Sliding window approach to find the minimum // operations while (j < n) { sum += nums[j]; // If the current sum is greater than the target // difference, move the window's left end (i) to // reduce the sum while (i < j && sum > totalSum) { sum -= nums[i]; i++; } // If the current sum equals the target // difference, update the answer with the // maximum window size if (sum == totalSum) { ans = Math.max(ans, j - i + 1); } j++; } // If 'ans' is still 0, it means no subarray with // the target sum was found return ans == 0 ? -1 : n - ans; } public static void main(String[] args) { Solution solution = new Solution(); int[] nums = { 1, 1, 4, 2, 3 }; int x = 5; int result = solution.minOperations(nums, x); if (result == -1) { System.out.println("No solution found."); } else { System.out.println( "Minimum operations required: " + result); } }}// This code is contributed by Abhinav Mahajan// (abhinav_m22) |
Python3
class Solution: def min_operations(self, nums, x): n = len(nums) total_sum = sum(nums) # If the total sum is equal to 'x', no operations are needed if total_sum == x: return n # Calculate the difference between the total sum and 'x' total_sum -= x i, j = 0, 0 curr_sum = 0 ans = 0 # Sliding window approach to find the minimum operations while j < n: curr_sum += nums[j] # If the current sum is greater than the target difference, # move the window's left end (i) to reduce the sum while i < j and curr_sum > total_sum: curr_sum -= nums[i] i += 1 # If the current sum equals the target difference, # update the answer with the maximum window size if curr_sum == total_sum: ans = max(ans, j - i + 1) j += 1 # If 'ans' is still 0, it means no subarray with the target sum was found return -1 if ans == 0 else n - ans# Driver codeif __name__ == "__main__": solution = Solution() nums = [1, 1, 4, 2, 3] x = 5 result = solution.min_operations(nums, x) if result == -1: print("No solution found.") else: print("Minimum operations required:", result) |
C#
// C++ Code for the above approach:using System;using System.Collections.Generic;class Solution { static int minOperations(List<int> nums, int x) { int n = nums.Count; int totalS = 0; int i, j; // Calculate the total sum of the // elements in the vector 'nums' for (i = 0; i < n; i++) { totalS += nums[i]; } // If the total sum is equal to 'x', // no operations are needed if (totalS == x) { return n; } // Calculate the difference between // the total sum and 'x' totalS = totalS - x; i = 0; j = 0; int sum = 0; int ans = 0; // Sliding window approach to find // the minimum operations while (j < n) { sum += nums[j]; // If the current sum is greater // than the target difference, move // the window's left end (i) to // reduce the sum while (i < j && sum > totalS) { sum -= nums[i]; i++; } // If the current sum equals the // target difference, update the // answer with the maximum // window size if (sum == totalS) { ans = Math.Max(ans, j - i + 1); } j++; } // If 'ans' is still 0, it means no // subarray with the target sum was found return ans == 0 ? -1 : n - ans; } // Drivers code public static void Main() { List<int> nums = new List<int>{ 1, 1, 4, 2, 3 }; int x = 5; int result = minOperations(nums, x); if (result == -1) { Console.WriteLine("No solution found."); } else { Console.WriteLine( "Minimum operations required: " + result); } }}// This code is contributed by ragul21 |
Javascript
class GFG { minOperations(nums, x) { const n = nums.length; let totalSum = 0; // Calculate the total sum of elements in the array 'nums' for (let i = 0; i < n; i++) { totalSum += nums[i]; } // If the total sum is equal to 'x' // no operations are needed if (totalSum === x) { return n; } // Calculate the difference between total sum and 'x' totalSum = totalSum - x; let i = 0; let j = 0; let sum = 0; let ans = 0; // Sliding window approach to find the minimum operations while (j < n) { sum += nums[j]; // If the current sum is greater than the target difference // move the window's left end (i) to reduce the sum while (i < j && sum > totalSum) { sum -= nums[i]; i++; } // If the current sum equals the target difference // update the answer with the maximum window size if (sum === totalSum) { ans = Math.max(ans, j - i + 1); } j++; } // If 'ans' is still 0, it means no subarray with target sum was found return ans === 0 ? -1 : n - ans; }}// Example usageconst solution = new GFG();const nums = [1, 1, 4, 2, 3];const x = 5;const result = solution.minOperations(nums, x);if (result === -1) { console.log("No solution found.");} else { console.log("Minimum operations required: " + result);} |
Output
Minimum operations required: 2
Time Complexity: O(n)
Auxillary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
