Minimum Maximum Value

Hard
0/120
profile
Contributed by
10 upvotes
Asked in company
Microsoft

Problem statement

You are given a mathematical expression ‘exp’ consisting of only two operators ‘+’ and ‘*’. You have to find the maximum and minimum value possible of the expression by placing valid parentheses anywhere in the expression.

For example: 
You are given ‘exp’ = 1*2+4*5+3, here the minimum and maximum value of the expression occurs when , (1*2) + (4*5) + 3 = 25, and   1*(2 + 4) *(5 + 3) = 48. Hence the answer is [25, 48].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a string ‘exp’ representing the expression given.
Output Format: 
For each test case, print two space-separated integers representing the maximum and minimum value of equations respectively.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= |exp| <= 100

Time Limit: 1 sec
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
2
1*2+4*5+3
2*3+4+1*5
Sample Output 1:
25 48
15 80
Explanation:
For the first test case, ‘exp’ = 1*2+4*5+3, here the minimum and maximum values of the expression occurs when , (1*2) + (4*5) + 3 = 25, and  1*(2 + 4) *(5 + 3) = 48. Hence the answer is [25, 48]

For the second test case, ‘exp’ = 2*3+4+1*5, here the minimum and maximum values of the expression occur when, (2*3) + 4 + (1*5) = 15, and 2*(3 + 4 + 1)*5 = 80. Hence the answer is [15, 80].
Sample input 2:
2
2*3+4
2*3+1*5*4
Sample Output 2:
10 14
26 160
Hint

Try to do this recursively

Approaches (3)
Recursive Solution

In this approach, we will recursively find the maximum and minimum value of every possible subexpression in the given expression. 

To find the maximum/minimum value of the subexpression ‘exp[startIndex, endIndex]’, starting at the position, ‘startIndex’ and ending at ‘endIndex’, we can iterate over the subexpression and if we find an operator at position ‘i’, we can find add/multiply the subexpressions exp[startIndex, i - 1] and exp[i + 1, endIndex], we take the maximum/minimum of all the positions when we find an operand, in the subexpression.

 

We create two functions maxValue(startIndex, endIndex, exp) and minValue(startIndex, endIndex, exp), where startIndex and endIndex are starting and ending indices of the subexpression of ‘exp’.

 

The only difference between the functions is that in maxValue we are taking the maximum of all subexpressions, while in minValue we are taking the minimum of all expressions.

 

Algorithm:

  • In the function maxValue(startIndex, endIndex, exp):
    • If startIndex is greater than endIndex return 0
    • If startIndex is equal to endIndex
      • Convert the exp[startIndex] to integer and return it.
    • Set maxAns as negative infinity
    • Iterate i from startIndex to endIndex
      • Set currVal as 0
      • If exp[i] is equal to  ‘+’
        • Set currVal as maxValue(startIndex, i - 1) + maxValue(i + 1, endIndex
      • If exp[i] is equal to  ‘*’
        • Set currVal as maxValue(startIndex, i - 1) * maxValue(i + 1, endIndex
      • Set maxAns as maximum of maxAns and currVal
    • Return maxAns
  • In the function minValue(startIndex, endIndex, exp):
    • If startIndex is greater than endIndex return 0
    • If startIndex is equal to endIndex
      • Convert the exp[startIndex] to integer and return it.
    • Set minAns as infinity
    • Iterate i from startIndex to endIndex
      • Set currVal as 0
      • If exp[i] is equal to  ‘+’
        • Set currVal as minValue(startIndex, i - 1, exp) + minValue(i + 1, endIndex, exp)
      • If exp[i] is equal to  ‘*’
        • Set currVal as minValue(startIndex, i - 1, exp) * minValue(i + 1, endIndex, exp)
      • Set minAns as minimum of minAns and currVal
    • Return minAns
  • In the original function:
    • Set minAns as minValue(0, length of exp - 1, exp)
    • Set maxAns as maxValue(0, length of exp - 1, exp)
    • Return [minAns, maxAns]
Time Complexity

O(N*(2^N)), Where N is the length of the expression.
 

We are iterating over the range of expression, which will cost O(N) time, each time we find an operator we have to make two separate function calls, Hence the overall time complexity is O(N)*O(2^N) = O(N*(2^N))

Space Complexity

O(N), Where N is the length of the expression

 

The space complexity of the recursion stack will go in the worst case up to O(N). Hence the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Maximum Value
Full screen
Console