Queries to find minimum sum of array elements from either end of an array | C ++ implementation of the above approach ; Function to find the minimum sum for the given queries ; Stores prefix and suffix sums ; Stores pairs of prefix and suffix sums ; Traverse the array ; Add element to prefix ; Store prefix for each element ; Traverse the array in reverse ; Add element to suffix ; Storing suffix for each element ; Traverse the array queries [ ] ; Minimum of suffix and prefix sums ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void calculateQuery ( int arr [ ] , int N , int query [ ] , int M ) { int prefix = 0 , suffix = 0 ; unordered_map < int , pair < int , int > > mp ; for ( int i = 0 ; i < N ; i ++ ) { prefix += arr [ i ] ; mp [ arr [ i ] ] . first = prefix ; } for ( int i = N - 1 ; i >= 0 ; i -- ) { suffix += arr [ i ] ; mp [ arr [ i ] ] . second = suffix ; } for ( int i = 0 ; i < M ; i ++ ) { int X = query [ i ] ; cout << min ( mp [ X ] . first , mp [ X ] . second ) << " ▁ " ; } } int main ( ) { int arr [ ] = { 2 , 3 , 6 , 7 , 4 , 5 , 30 } ; int queries [ ] = { 6 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int M = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; calculateQuery ( arr , N , queries , M ) ; return 0 ; }