Minimize Result by Adding Parentheses to Expression Solution – LeetCode

Problem: Minimize Result by Adding Parentheses to Expression Solution

You are given a 0-indexed string expression of the form "<num1> <num2>" where <num1> and <num2> represent positive integers.

Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.

Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Example 1:

Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.

Example 2:

Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.

Example 3:

Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.

Constraints:

  • 3 <= expression.length <= 10
  • expression consists of digits from '1' to '9' and '+'.
  • expression starts and ends with digits.
  • expression contains exactly one '+'.
  • The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Minimize Result by Adding Parentheses to Expression Solution

class Solution {
public:
    string minimizeResult(string expr) {
        //First find the index of '+ in expresseion. let it be idx.
		int idx;
        int n=expr.size();
        for(int i=0;i<n;i++)
            if(expr[i]=='+')
            {
                idx=i;
                break;
            }
			
		//Now find two numbers which are on left and right side of '+' sign in expression	
        string num1 = expr.substr(0,idx);
        string num2 = expr.substr(idx+1,n-idx-1);
		
		//b1 and b2 are for brackets . b1=left bracket, b2=right bracket
        int b1=0,b2=0;
        int min =INT_MAX;
        string ans;
		
		//p1 and p2 are product number outside the brackets i.e our expresion is p1(sum)p2
        int p1,p2;
		
		//Find all possible conditions, iterate left bracket over num1 and right bracket over num2
        for(int b1=0;b1<num1.size();b1++)
        {
            for(int b2=0;b2<num2.size();b2++)
            {
                // s1 and s2 are strings which are outside the left parenthesis and right parenthesis respectively 
                string s1=num1.substr(0,b1);
                string s2=num2.substr(b2+1,b2-num2.size()-1);
               
               //if any of the string is empty then its int value should be 1 else its same as string.
			   if(s1.empty())
                    p1=1;
                else
                    p1=stoi(num1.substr(0,b1));
                if(s2.empty())
                    p2=1;
                else
                    p2=stoi(num2.substr(b2+1,b2-num2.size()-1));
					
				//sum stores the numerical value of the sum between the parenthesis	
                int sum=stoi(num1.substr(b1,num1.size())) + stoi(num2.substr(0,b2+1));
               //eval stores the numerical value of whole expression
			   int eval=p1*sum*p2;
			   
			   //if velue of expression is less then minimum, then make ans string = s1(sum) s1
                if(eval<min){
                    
                    min=eval;
                    ans=s1+"("+num1.substr(b1,num1.size())+"+"+num2.substr(0,b2+1)+")"+s2;
                
                }
                
            }
        }
        return ans;
        //return final string
        
    }
};

Minimize Result by Adding Parentheses to Expression Solution

Minimize Result by Adding Parentheses to Expression Solution Review:

In our experience, we suggest you solve this Minimize Result by Adding Parentheses to Expression Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

Minimize Result by Adding Parentheses to Expression Solution is available on Leetcode for Free, if you are stuck anywhere between compilation, just visit Queslers to get the Minimize Result by Adding Parentheses to Expression Solution.

Conclusion:

I hope this Minimize Result by Adding Parentheses to Expression Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Hacker Rank Problem & Solutions >>

Staircase Hacker Rank Solution

A Very Big Sum Hacker Rank Solution

Diagonal Difference Hacker Rank Solution

Nested Lists Hacker Rank Solution

Lists Hacker Rank Solution

Leave a Reply

Your email address will not be published.