{"id":715,"date":"2020-06-10T11:41:50","date_gmt":"2020-06-10T11:41:50","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=715"},"modified":"2022-04-08T11:00:36","modified_gmt":"2022-04-08T11:00:36","slug":"aman-and-math","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/aman-and-math\/","title":{"rendered":"Aman and Math"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Strings<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

Find the maximum answer by evaluating the given string and putting a bracket anywhere in the string.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h4>\n
    Input:\n    2\n    3+4*5+6\n    3*5+6*7+2\n\n    Output:\n    47\n    233\n\n    Explanation:\n    Case-1:\n    We can put brackets at last operator making equation as 3+4*(5+6) => 3+4*11 => 47.\n\n    Case-2:\n    We can put bracket at 2nd operator making equation as 3*(5+6)*7+2 => 3*11*7+2 => 33*7+2 => 231+2 => 233.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/h4>\n
\n
1) We can place brackets at all possible positions and check the value of all possible cases and then we can find the maximum value out of them, thus we print the maximum value.
\n2) Evaluating string of size L<\/code> takes O(N)<\/code> time, where checking all possibilities take O(M)<\/code> times where M is the number of operators i.e. *<\/code> or +<\/code> in whole string. So this approach takes total O(M\\times N)<\/code> time complexity. The above approach takes a long time to evaluate strings of larger sizes. So we search for an optimized approach that can solve this problem in a shorter time.<\/p>\n<\/blockquote>\n
Efficient Approach:<\/h4>\n
\n
1) An easy analysis shows that the brackets must be placed adjacent to *<\/code> sign since they won’t have any effect next to a +<\/code> sign.
\n2) We need to store the indexes of all the *<\/code> in the string and iterate over all possible pairs. One thing to keep in mind is the maximum case may be one in which the brackets start at the 0th index or the one in which it ends at the last index.<\/p>\n<\/blockquote>\n
Example<\/h3>\n
\n
    \n
  • Lets assume given equation is 3*5+6*7+2<\/code>.<\/li>\n
  • As discussed in Step-1<\/code>, the equation will be maximized if we put brackets adjacent to a multiplication operator. So we get two possibilities here, that is, 3*(5+6)*7+2<\/code> and 3*5+6*(7+2)<\/code>.<\/li>\n
  • On evaluating above equations, equations yield 233<\/code> and 69<\/code> respectively, where the first equation yields the maximum value. So it is our final answer.<\/li>\n<\/ul>\n<\/blockquote>\n
    Solutions<\/h3>\n\t\t\t\t\t\t