Queries to find the minimum array sum possible by removing elements from either end
Given an array arr[] consisting of N distinct integers and an array Q[] representing queries, the task for every query Q[i] is to find the minimum sum possible by removing the array elements from either end until Q[i] is obtained.
Examples:
Input: arr[] = {2, 3, 6, 7, 4, 5, 1}, Q[] = {7, 6}
Output: 17 11
Explanation:
Query 1: By popping elements from the end, sum = 1 + 5 + 4 + 7 = 17.
Query 2: Popping elements from the front, sum = 2 + 3 + 6 = 11.Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Q[] = {4, 6, 3}
Output: 10 21 6
Naive Approach: The simplest approach to solve the given problem is to traverse the given array from both the ends for each query Q[i] and print the minimum sum obtained from both the traversals till the element with value Q[i] is obtained.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum sum for // each query after removing elements // from either ends void minSum( int arr[], int N, int Q[], int M) { // Traverse the query array for ( int i = 0; i < M; i++) { int val = Q[i]; int front = 0, rear = 0; // Traverse the array from // the front for ( int j = 0; j < N; j++) { front += arr[j]; // If element equals val, // then break out of loop if (arr[j] == val) { break ; } } // Traverse the array from rear for ( int j = N - 1; j >= 0; j--) { rear += arr[j]; // If element equals val, break if (arr[j] == val) { break ; } } // Print the minimum of the // two as the answer cout << min(front, rear) << " " ; } } // Driver Code int main() { int arr[] = { 2, 3, 6, 7, 4, 5, 1 }; int N = sizeof (arr) / sizeof (arr[0]); int Q[] = { 7, 6 }; int M = sizeof (Q) / sizeof (Q[0]); // Function Call minSum(arr, N, Q, M); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the minimum sum for // each query after removing elements // from either ends static void minSum( int arr[], int N, int Q[], int M) { // Traverse the query array for ( int i = 0 ; i < M; i++) { int val = Q[i]; int front = 0 , rear = 0 ; // Traverse the array from // the front for ( int j = 0 ; j < N; j++) { front += arr[j]; // If element equals val, // then break out of loop if (arr[j] == val) { break ; } } // Traverse the array from rear for ( int j = N - 1 ; j >= 0 ; j--) { rear += arr[j]; // If element equals val, break if (arr[j] == val) { break ; } } // Print the minimum of the // two as the answer System.out.print(Math.min(front, rear) + " " ); } } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 3 , 6 , 7 , 4 , 5 , 1 }; int N = arr.length; int Q[] = { 7 , 6 }; int M = Q.length; // Function Call minSum(arr, N, Q, M); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach # Function to find the minimum sum for # each query after removing elements # from either ends def minSum(arr, N, Q, M): # Traverse the query array for i in range (M): val = Q[i] front, rear = 0 , 0 # Traverse the array from # the front for j in range (N): front + = arr[j] # If element equals val, # then break out of loop if (arr[j] = = val): break # Traverse the array from rear for j in range (N - 1 , - 1 , - 1 ): rear + = arr[j] # If element equals val, break if (arr[j] = = val): break # Print the minimum of the # two as the answer print ( min (front, rear), end = " " ) # Driver Code if __name__ = = '__main__' : arr = [ 2 , 3 , 6 , 7 , 4 , 5 , 1 ] N = len (arr) Q = [ 7 , 6 ] M = len (Q) # Function Call minSum(arr, N, Q, M) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG{ // Function to find the minimum sum for // each query after removing elements // from either ends static void minSum( int [] arr, int N, int [] Q, int M) { // Traverse the query array for ( int i = 0; i < M; i++) { int val = Q[i]; int front = 0, rear = 0; // Traverse the array from // the front for ( int j = 0; j < N; j++) { front += arr[j]; // If element equals val, // then break out of loop if (arr[j] == val) { break ; } } // Traverse the array from rear for ( int j = N - 1; j >= 0; j--) { rear += arr[j]; // If element equals val, break if (arr[j] == val) { break ; } } // Print the minimum of the // two as the answer Console.Write(Math.Min(front, rear) + " " ); } } // Driver Code static public void Main() { int [] arr = { 2, 3, 6, 7, 4, 5, 1 }; int N = arr.Length; int [] Q = { 7, 6 }; int M = Q.Length; // Function Call minSum(arr, N, Q, M); } } // This code is contributed by rag2127 |
Javascript
<script> // Javascript program for the above approach // Function to find the minimum sum for // each query after removing elements // from either ends function minSum(arr, N, Q, M) { // Traverse the query array for ( var i = 0; i < M; i++) { var val = Q[i]; var front = 0, rear = 0; // Traverse the array from // the front for ( var j = 0; j < N; j++) { front += arr[j]; // If element equals val, // then break out of loop if (arr[j] == val) { break ; } } // Traverse the array from rear for ( var j = N - 1; j >= 0; j--) { rear += arr[j]; // If element equals val, break if (arr[j] == val) { break ; } } // Print the minimum of the // two as the answer document.write( Math.min(front, rear) + " " ); } } var arr = [ 2, 3, 6, 7, 4, 5, 1 ]; var N = arr.length; var Q = [ 7, 6 ]; var M = Q.length; // Function Call minSum(arr, N, Q, M); // This code is contributed by SoumikMondal </script> |
17 11
Time Complexity: O(N*M)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use the Prefix Sum technique to solve this problem. Follow the steps below to solve the problem:
- Create two auxiliary Maps, say M1 and M2.
- Traverse the array from the front and insert the current sum calculated till each index in the Map M1 along with the element.
- Similarly, traverse the array from the back and insert the current sum calculated till each index in the map M2 along with the element.
- Traverse the array Q[] and for each element Q[i], print minimum of M1[Q[i]] and M2[Q[i]] as the minimum possible sum.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum sum // for each query after removing // element from either ends till each // value Q[i] void minOperations( int arr[], int N, int Q[], int M) { // Stores the prefix sum from // both the ends of the array map< int , int > m1, m2; int front = 0, rear = 0; // Traverse the array from front for ( int i = 0; i < N; i++) { front += arr[i]; // Insert it into the map m1 m1.insert({ arr[i], front }); } // Traverse the array in reverse for ( int i = N - 1; i >= 0; i--) { rear += arr[i]; // Insert it into the map m2 m2.insert({ arr[i], rear }); } // Traverse the query array for ( int i = 0; i < M; i++) { // Print the minimum of the // two values as the answer cout << min(m1[Q[i]], m2[Q[i]]) << " " ; } } // Driver Code int main() { int arr[] = { 2, 3, 6, 7, 4, 5, 1 }; int N = sizeof (arr) / sizeof (arr[0]); int Q[] = { 7, 6 }; int M = sizeof (Q) / sizeof (Q[0]); // Function Call minOperations(arr, N, Q, M); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the minimum sum // for each query after removing // element from either ends till each // value Q[i] static void minOperations( int [] arr, int N, int [] Q, int M) { // Stores the prefix sum from // both the ends of the array Map<Integer, Integer> m1 = new HashMap<Integer, Integer>(); Map<Integer, Integer> m2 = new HashMap<Integer, Integer>(); int front = 0 , rear = 0 ; // Traverse the array from front for ( int i = 0 ; i < N; i++) { front += arr[i]; // Insert it into the map m1 m1.put(arr[i], front); } // Traverse the array in reverse for ( int i = N - 1 ; i >= 0 ; i--) { rear += arr[i]; // Insert it into the map m2 m2.put(arr[i], rear); } // Traverse the query array for ( int i = 0 ; i < M; i++) { // Print the minimum of the // two values as the answer System.out.print(Math.min(m1.get(Q[i]), m2.get(Q[i])) + " " ); } } // Driver code public static void main(String[] args) { int [] arr = { 2 , 3 , 6 , 7 , 4 , 5 , 1 }; int N = arr.length; int [] Q = { 7 , 6 }; int M = Q.length; // Function Call minOperations(arr, N, Q, M); } } // This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function to find the minimum sum # for each query after removing # element from either ends till each # value Q[i] def minOperations(arr, N, Q, M): # Stores the prefix sum from # both the ends of the array m1 = {} m2 = {} front = 0 rear = 0 # Traverse the array from front for i in range (N): front + = arr[i] # Insert it into the map m1 m1[arr[i]] = front # Traverse the array in reverse for i in range (N - 1 , - 1 , - 1 ): rear + = arr[i] # Insert it into the map m2 m2[arr[i]] = rear # Traverse the query array for i in range (M): # Print the minimum of the # two values as the answer print ( min (m1[Q[i]], m2[Q[i]]),end = " " ) # Driver Code arr = [ 2 , 3 , 6 , 7 , 4 , 5 , 1 ] N = len (arr) Q = [ 7 , 6 ] M = len (Q) # Function Call minOperations(arr, N, Q, M) # This code is contributed by avanitrachhadiya2155 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the minimum sum // for each query after removing // element from either ends till each // value Q[i] static void minOperations( int [] arr, int N, int [] Q, int M) { // Stores the prefix sum from // both the ends of the array Dictionary< int , int > m1 = new Dictionary< int , int >(); Dictionary< int , int > m2 = new Dictionary< int , int >(); int front = 0, rear = 0; // Traverse the array from front for ( int i = 0; i < N; i++) { front += arr[i]; // Insert it into the map m1 m1[arr[i]] = front; } // Traverse the array in reverse for ( int i = N - 1; i >= 0; i--) { rear += arr[i]; // Insert it into the map m2 m2[arr[i]] = rear; } // Traverse the query array for ( int i = 0; i < M; i++) { // Print the minimum of the // two values as the answer Console.Write(Math.Min(m1[Q[i]], m2[Q[i]]) + " " ); } } // Driver Code public static void Main() { int [] arr = { 2, 3, 6, 7, 4, 5, 1 }; int N = arr.Length; int [] Q = { 7, 6 }; int M = Q.Length; // Function Call minOperations(arr, N, Q, M); } } // This code is contributed by ukasp |
Javascript
<script> // javascript program for the above approach // Function to find the minimum sum // for each query after removing // element from either ends till each // value Q[i] function minOperations(arr, N, Q, M) { // Stores the prefix sum from // both the ends of the array var m1 = new Map(); var m2 = new Map(); var front = 0, rear = 0; var i; // Traverse the array from front for (i = 0; i < N; i++) { front += arr[i]; // Insert it into the map m1 m1.set(arr[i],front); } // Traverse the array in reverse for (i = N - 1; i >= 0; i--) { rear += arr[i]; // Insert it into the map m2 m2.set(arr[i], rear); } // Traverse the query array for (i = 0; i < M; i++) { // Print the minimum of the // two values as the answer document.write(Math.min(m1.get(Q[i]), m2.get(Q[i])) + " " ); } } // Driver Code var arr = [2, 3, 6, 7, 4, 5, 1]; var N = arr.length; var Q = [7, 6]; var M = Q.length; // Function Call minOperations(arr, N, Q, M); // This code is contributed by ipg2016107. </script> |
17 11
Time Complexity: O(N + M)
Auxiliary Space: O(N)
Contact Us