Minimum and Maximum values of an expression with * and +

Introduction

In this article, we will go through a very interesting problem to find the maximum and minimum value of an expression with + and *.
 

Before starting, let me tell you the important goals which we will achieve through this blog-

  • The first one is that you will learn how to solve this problem, which is why you are here. 
  • Secondly and most importantly, you will learn how to approach an unknown question and build your solution. Because believe me, everyone can solve every question; it is just the right direction you have to head. So, in short, you will learn the art of problem-solving.
  • And Bonus point - You will see how to optimize your brute force solution to get an efficient solution.
     

Finally, without much ado, let's get started with the problem statement.

Problem Statement

Given an expression that contains numbers and two operators ‘+’ and ‘*’, we need to find the maximum and minimum values, which can be obtained by evaluating this expression by different parenthesization. 

 

Please try to solve this problem on your own before moving on to the further discussion
 

The expression here implies a mathematical expression consisting of integers and operators. In our case, we have only two operators in the expression: addition(+) and multiplication(*). 
 

Let’s take an example of a simple expression E = 2+7*5

  • It has 2 operators: one + and one * where E[1]=+ and E[3]=*
  • The possible parenthesizations and the corresponding values are - 
  • E = (2+7)*5 = 9*5 = 45
  • E = 2+(7*5) = 2+35 = 37
  • So, the minimum value is 37, and the maximum value is 45.

 

This problem is quite similar to the matrix chain multiplication problem. We need to parenthesize the given expression to obtain the maximum/minimum value.

 

One way is to try out all the possible parenthesizations of the expression and keep an account of the evaluated values. So, in this way, we will find the maximum and the minimum among all the possible values. For every operator, we will evaluate the part of the expression on its left side and its right side, respectively. Say, the values are ELeft and ERight, respectively. So if the operator is +, then the value of E will be ELeft + ERight, or if it is *, then E will be ELeft*ERight

Now, to maximize E, both the ELeft and ERight should also be maximized. Why? The addition of ELeft and ERight will be maximum when both the ELeft and ERight are maximum. Similarly, the multiplication of two maximum values will also be maximum. 

So, to solve the expression E, we need to solve two similar subproblems ELeft and ERight. Hence, we get a recursive relationship. 

 

What is the base case of the recursion?

If the length of the expression is 1, which means if the expression consists of only a single integer without any operator, then the value of the expression is the integer itself.

Example - If expression E = “1”, then the value of E is 1.

Now, let’s see the algorithm step by step.

Recursive Algorithm

  1. Define a recursive function to find the maximum/minimum value of the expression starting from index=i and ending at index=j.
     
  2. Iterate over the expression from k=i+1 to k=j-1 and increment k by 2 in each iteration so that E[k] is always an operator.
     
  3. For every k, compute the value of the expression ELeftE[i,k-1] and ERight = E[k+1,j]
     
  4. Define a variable temp to store the value of the expression for the current parenthesization and a variable ans to store the optimal value of the expression.
     
  5. If E[k] is +, then temp=ELeft+ERight else temp=ELeft*ERight. Compare temp with ans and update ans if required. If you need the maximum value of the expression and ans < temp, then update ans as ans = temp and vice versa for the minimum value.

By now, you must have understood the idea about the recursive approach. If not, then don’t worry. In the next section, we will see the implementation of the recursive approach along with time and space constraints which will improve your understanding of the problem.

C++ Implementation

/*C++ implementation of the problem to find the minimum and maximum value
of an expression with + and * */
#include <bits/stdc++.h>
using namespace std;


int evalExpressionMin(int i, int j, string str)
{
    if (i > j)
        return 0;


    if (i == j)
    {
        return str[i] - '0';
    }


    int ans = INT_MAX;
    for (int k = i + 1; k <= j - 1; k = k + 2)
    {
        int tempAns = 0, ELeft = 0, ERight = 0;
        ELeft = evalExpressionMin(i, k - 1, str);
        ERight = evalExpressionMin(k + 1, j, str);


        if (str[k] == '+')
            tempAns = ELeft + ERight;
        if (str[k] == '*')
            tempAns = ELeft * ERight;
        ans = min(ans, tempAns);
    }
    return ans;
}


int evalExpressionMax(int i, int j, string str)
{
    if (i > j)
        return 0;


    if (i == j)
        return str[i] - '0';


    int ans = INT_MIN;
    for (int k = i + 1; k <= j - 1; k = k + 2)
    {
        int tempAns = 0, ELeft = 0, ERight = 0;
        ELeft = evalExpressionMax(i, k - 1, str);
        ERight = evalExpressionMax(k + 1, j, str);
        if (str[k] == '+')
            tempAns = ELeft + ERight;
        if (str[k] == '*')
            tempAns = ELeft * ERight;
        ans = max(ans, tempAns);
    }
    return ans;
}


int main()
{
    string S = "1+2*3+4*5";
    int N = S.size();
    int minn = evalExpressionMin(0, N - 1, S);
    int maxx = evalExpressionMax(0, N - 1, S);
    cout << "Minimum Value is " << minn << endl
         << "Maximum Value is " << maxx << endl;
    return 0;
}

Output

Minimum Value is 27
Maximum Value is 105

Time Complexity

The time complexity of the recursive approach is exponential. As, if you observe, the recurrence relation is - 

E[i,j] = E[0]-’0’ if i==j
else
E[i,j] = min( E[i,k-1] operator E[k+1,j]) for all k=i+1 to k=j-1 

Space Complexity 

If we consider the recursion stack space, the space complexity will be O(n) because the maximum depth of the recursion will be n, and in each recursive call, we don't use any extra space. So, it is n*O(1) which is nothing but O(n).

Dynamic Programming Approach

The recursive solution solves many subproblems repeatedly, and as a result, it is not time efficient. So, if we want to optimize the solution, one way is to avoid the repetitive computation of the same subproblem and improve the time complexity. How do we do that? 

We will store the result of every subproblem once it is solved, and afterwards, if we encounter the same subproblem again, we will reuse the stored result and won't compute it again.

We will consider the bottom-up approach, which implies we will start by solving smaller subproblems and use them to compute larger subproblems.

 

Let’s see the code implementation and the time and space complexity analysis in the next section.

C++ Implementation

/*C++ implementation of the problem to find the minimum and maximum value
of an expression with + and * */
#include <bits/stdc++.h>
using namespace std;


// function to check if a given character is an operator or not
bool isOperator(char op)
{
    return (op == '+' || op == '*');
}


void minMaxValExpression(string E)
{
    string temp = "";
    vector<int> numbers;    // stores the numbers from the exression
    vector<char> operators; // stores the operators from the exression


    for (int i = 0; i < E.length(); i++)
    {
        if (isOperator(E[i]))
        {
            operators.push_back(E[i]);
            numbers.push_back(atoi(temp.c_str()));
            temp = "";
        }
        else
        {
            temp += E[i];
        }
    }


    numbers.push_back(atoi(temp.c_str()));


    int length = numbers.size();
    int minValExp[length][length];
    int maxValExp[length][length];


    // initializing the 2d arrays minValExp and maxValExp
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < length; j++)
        {
            minValExp[i][j] = INT_MAX;
            maxValExp[i][j] = 0;


            // for an expression of length 1 i.e. i=j
            if (i == j)
                minValExp[i][j] = maxValExp[i][j] = numbers[i];
        }
    }


    for (int L = 2; L <= length; L++)
    {
        for (int i = 0; i < length - L + 1; i++)
        {
            int j = i + L - 1;
            for (int k = i; k < j; k++)
            {
                int tempMin = 0, tempMax = 0;
                if (operators[k] == '*')
                {
                    tempMin = minValExp[i][k] * minValExp[k + 1][j];
                    tempMax = maxValExp[i][k] * maxValExp[k + 1][j];
                }
                else if (operators[k] == '+')
                {
                    tempMin = minValExp[i][k] + minValExp[k + 1][j];
                    tempMax = maxValExp[i][k] + maxValExp[k + 1][j];
                }


                if (tempMin < minValExp[i][j])
                    minValExp[i][j] = tempMin;
                if (tempMax > maxValExp[i][j])
                    maxValExp[i][j] = tempMax;
            }
        }
    }


    cout << "Minimum value is " << minValExp[0][length - 1]
         << "\nMaximum value is " << maxValExp[0][length - 1];
}


int main()
{
    string E = "1+2*3+4*5";
    minMaxValExpression(E);
    return 0;
}

 

Output

Minimum Value of the expression is 27
Maximum Value of the expression is 105

Time Complexity

O(n^3), as we have three nested loops in the function.

Space Complexity 

O(n^2), since we are using a 2D matrix to store the values of all the subproblems.

Frequently Asked Questions

  1. Is recursion important for coding interviews?
    Recursion is the foundation of logic, local variables, the call-stack, and much more. It utilises a logic-driven intuitive cognitive approach. One of the most prevalent reasons individuals want to comprehend recursion is frequently asked during interviews.
     
  2. What is Dynamic Programming?
    Dynamic programming is an optimization for recursion. We have to calculate the same calculation repeatedly, making a stack going in-depth, but using DP, we can overcome this problem.

Key Takeaways

In this article, we learnt to solve the problem to find the minimum and maximum value of an expression with + and *. We started with a very intuitive brute force approach, and we obtained a very beautiful recursive solution. Then based upon our understanding, we observed the brute force solution's inefficiency, so we optimized it through memoization. 
 

You must have got an idea about problem-solving in this blog. But without practice, your learning is incomplete. Keep practising and keep challenging yourself with new problems on Codestudio. 

We also have guided paths especially curated for you, which is your one-stop solution for any topic you have always wanted to learn most intuitively and easily.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!

Was this article helpful ?
2 upvotes

Comments

No comments yet

Be the first to share what you think