Minimum number that can be obtained by applying ' + ' and ' * ' operations on array elements | C ++ program for the above approach ; Function to find the smallest number that can be obtained after applying the arithmetic operations mentioned in the string S ; Stores the count of multiplication operator in the string ; Store the required result ; Iterate in the range to create the mask ; Checking the number of bits that are set in the mask ; Check if the number of bits that are set in the mask is multiplication operation ; Storing the elements that is to be added ; Apply the multiplications operation first ; If sign is ' * ' , then multiply last element of deque with arr [ i ] ; Push last multiplied element in the deque ; If the element is to be added , then add it to the deque ; Add all the element of the deque ; Minimize the answer with the given sum ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minimumSum ( int A [ ] , int N , string S ) { int mul = 0 ; for ( int i = 0 ; i < ( int ) S . size ( ) ; i ++ ) { if ( S [ i ] == ' * ' ) mul += 1 ; } int ans = 1000000 ; for ( int i = 0 ; i < ( 1 << ( N - 1 ) ) ; i ++ ) { int cnt = 0 ; vector < char > v ; for ( int j = 0 ; j < N - 1 ; j ++ ) { if ( ( 1 << j ) & ( i ) ) { cnt += 1 ; v . push_back ( ' * ' ) ; } else { v . push_back ( ' + ' ) ; } } if ( cnt == mul ) { deque < int > d ; d . push_back ( A [ 0 ] ) ; for ( int j = 0 ; j < N - 1 ; j ++ ) { if ( v [ j ] == ' * ' ) { int x = d . back ( ) ; d . pop_back ( ) ; x = x * A [ j + 1 ] ; d . push_back ( x ) ; } else { d . push_back ( A [ j + 1 ] ) ; } } int sum = 0 ; while ( d . size ( ) > 0 ) { int x = d . front ( ) ; sum += x ; d . pop_front ( ) ; } ans = min ( ans , sum ) ; } } return ans ; } int main ( ) { int A [ ] = { 2 , 2 , 2 , 2 } ; string S = " * * + " ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << minimumSum ( A , N , S ) ; return 0 ; }