Given an array arr[] consisting of N integers and an integer K, the task is to reduce K to 0 by removing an array element from either end of the array and subtracting it from K. If it is impossible to reduce K to 0, then print “-1”. Otherwise, print the minimum number of such operations required.
Examples:
Input: arr[] = {1, 3, 1, 1, 2}, K = 4
Output: 2
Explanation:
The given array is {1, 3, 1, 1, 2}
Operation1: Removing arr[0] (= 1) modifies arr[] to {3, 1, 1, 2}. Subtracting arr[0] from K reduces K to 4 – 1 = 3.
Operation2: Removing arr[0] (= 1) modifies arr[] to {1, 1, 2}. Subtracting arr[0] from K reduces K to 3 – 3 = 0.
Therefore, the total number of steps required is 2.Input: arr[] = {1, 1, 3, 4}, K = 3
Output: -1
Approach: The given problem can be solved based on the following observations:
- Consider that X and Y elements are required to be removed from the front and back of the given array respectively, to reduce K to 0.
- Therefore, sum of the remaining array elements must be equal to (sum of array elements – K).
Therefore, from the above observation, the idea is to find the maximum length of subarray (say L) whose sum is equal to (sum of array elements – K). Therefore, print the value of (N – L) as the resultant minimum element that must be removed to reduce K to 0. If there doesn’t exist any such subarray, then print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the length of// longest subarray having sum Kint longestSubarray(int arr[], int N, int K){ // Stores the index of // the prefix sum unordered_map<int, int> um; int sum = 0, maxLen = 0; // Traverse the given array for (int i = 0; i < N; i++) { // Update sum sum += arr[i]; // If the subarray starts // from index 0 if (sum == K) maxLen = i + 1; // Add the current prefix sum // with index if it is not // present in the map um if (um.find(sum) == um.end()) um[sum] = i; // Check if sum - K is // present in Map um or not if (um.find(sum - K) != um.end()) { // Update the maxLength if (maxLen < (i - um[sum - K])) maxLen = i - um[sum - K]; } } // Return the required maximum length return maxLen;}// Function to find the minimum removal of// array elements required to reduce K to 0void minRequiredOperation(int arr[], int N, int K){ // Stores the sum of the array int TotalSum = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) // Update sum of the array TotalSum += arr[i]; // Find maxLen int maxLen = longestSubarray( arr, N, TotalSum - K); // If the subarray with // sum doesn't exist if (maxLen == -1) { cout << -1; } // Otherwise, print the // required maximum length else cout << N - maxLen;}// Driver Codeint main(){ int arr[] = { 1, 3, 1, 1, 2 }; int K = 4; int N = sizeof(arr) / sizeof(arr[0]); minRequiredOperation(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the length of// longest subarray having sum Kstatic int longestSubarray(int[] arr, int N, int K){ // Stores the index of // the prefix sum HashMap<Integer, Integer> um = new HashMap<Integer, Integer>(); int sum = 0, maxLen = 0; // Traverse the given array for(int i = 0; i < N; i++) { // Update sum sum += arr[i]; // If the subarray starts // from index 0 if (sum == K) maxLen = i + 1; // Add the current prefix sum // with index if it is not // present in the map um if (!um.containsKey(sum)) um.put(sum, i); // Check if sum - K is // present in Map um or not if (um.containsKey(sum - K)) { // Update the maxLength if (maxLen < (i - um.get(sum - K))) maxLen = i - um.get(sum - K); } } // Return the required maximum length return maxLen;}// Function to find the minimum removal of// array elements required to reduce K to 0static void minRequiredOperation(int[] arr, int N, int K){ // Stores the sum of the array int TotalSum = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) // Update sum of the array TotalSum += arr[i]; // Find maxLen int maxLen = longestSubarray(arr, N, TotalSum - K); // If the subarray with // sum doesn't exist if (maxLen == -1) { System.out.println(-1); } // Otherwise, print the // required maximum length else System.out.println(N - maxLen);}// Driver Codepublic static void main(String[] args){ int[] arr = { 1, 3, 1, 1, 2 }; int K = 4; int N = arr.length; minRequiredOperation(arr, N, K);}}// This code is contributed by ukasp |
Python3
# Python3 program for the above approach# Function to find the length of# longest subarray having sum Kdef longestSubarray(arr, N, K): # Stores the index of # the prefix sum um = {} sum , maxLen = 0, 0 # Traverse the given array for i in range(N): # Update sum sum += arr[i] # If the subarray starts # from index 0 if (sum == K): maxLen = i + 1 # Add the current prefix sum # with index if it is not # present in the map um if (sum not in um): um[sum] = i # Check if sum - K is # present in Map um or not if ((sum - K) in um): # Update the maxLength if (maxLen < (i - um[sum - K])): maxLen = i - um[sum - K] # Return the required maximum length return maxLen# Function to find the minimum removal of# array elements required to reduce K to 0def minRequiredOperation(arr, N, K): # Stores the sum of the array TotalSum = 0 # Traverse the array arr[] for i in range(N): # Update sum of the array TotalSum += arr[i] # Find maxLen maxLen = longestSubarray(arr, N, TotalSum - K) # If the subarray with # sum doesn't exist if (maxLen == -1): print (-1,end="") # Otherwise, print the # required maximum length else: print (N - maxLen,end="")# Driver Codeif __name__ == '__main__': arr = [1, 3, 1, 1, 2] K = 4 N = len(arr) minRequiredOperation(arr, N, K) # this code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the length of // longest subarray having sum K static int longestSubarray(int []arr, int N, int K) { // Stores the index of // the prefix sum Dictionary<int,int> um = new Dictionary<int,int>(); int sum = 0, maxLen = 0; // Traverse the given array for (int i = 0; i < N; i++) { // Update sum sum += arr[i]; // If the subarray starts // from index 0 if (sum == K) maxLen = i + 1; // Add the current prefix sum // with index if it is not // present in the map um if (!um.ContainsKey(sum)) um[sum] = i; // Check if sum - K is // present in Map um or not if (um.ContainsKey(sum - K)) { // Update the maxLength if (maxLen < (i - um[sum - K])) maxLen = i - um[sum - K]; } } // Return the required maximum length return maxLen; } // Function to find the minimum removal of // array elements required to reduce K to 0 static void minRequiredOperation(int []arr, int N, int K) { // Stores the sum of the array int TotalSum = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) // Update sum of the array TotalSum += arr[i]; // Find maxLen int maxLen = longestSubarray( arr, N, TotalSum - K); // If the subarray with // sum doesn't exist if (maxLen == -1) { Console.WriteLine(-1); } // Otherwise, print the // required maximum length else Console.WriteLine(N - maxLen); } // Driver Code public static void Main() { int []arr = { 1, 3, 1, 1, 2 }; int K = 4; int N = arr.Length; minRequiredOperation(arr, N, K); }}// This code is contributed by SUREDRA_GANGWAR. |
Javascript
<script>// Javascript program for the above approach// Function to find the length of// longest subarray having sum Kfunction longestSubarray(arr, N, K){ // Stores the index of // the prefix sum let um = new Map(); let sum = 0, maxLen = 0; // Traverse the given array for(let i = 0; i < N; i++) { // Update sum sum += arr[i]; // If the subarray starts // from index 0 if (sum == K) maxLen = i + 1; // Add the current prefix sum // with index if it is not // present in the map um if (!um.has(sum)) um.set(sum, i); // Check if sum - K is // present in Map um or not if (um.has(sum - K)) { // Update the maxLength if (maxLen < (i - um.get(sum - K))) maxLen = i - um.get(sum - K); } } // Return the required maximum length return maxLen;}// Function to find the minimum removal of// array elements required to reduce K to 0function minRequiredOperation(arr, N, K) { // Stores the sum of the array let TotalSum = 0; // Traverse the array arr[] for(let i = 0; i < N; i++) // Update sum of the array TotalSum += arr[i]; // Find maxLen let maxLen = longestSubarray( arr, N, TotalSum - K); // If the subarray with // sum doesn't exist if (maxLen == -1) { document.write(-1); } // Otherwise, print the // required maximum length else document.write(N - maxLen);}// Driver Codelet arr = [ 1, 3, 1, 1, 2 ];let K = 4;let N = arr.lengthminRequiredOperation(arr, N, K);// This code is contributed by gfgking</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
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!