Insert parentheses to minimize expression value

Q: Insert parentheses to minimize expression value

This question evaluates string parsing, arithmetic expression modeling, and combinatorial optimization skills by requiring reasoning about how digit concatenation and parentheses placement alter multiplicative factors and the final numeric value.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given a string expression of the form A+B, where A and B are non-empty strings of digits (no digit is '0'). You must insert exactly one pair of parentheses ( and ) into the expression such that:

The parentheses form a valid expression and must include the plus sign .
Any digits outside the parentheses remain adjacent to the parentheses and are interpreted as multiplication with the parenthesized sum.

More precisely, choose a split of A into A = L1 + L2 (concatenation) and a split of B into B = R1 + R2 such that the resulting value is:

If L1 is empty, treat it as multiplicative factor 1; otherwise factor is integer value of L1 .
If R2 is empty, treat it as multiplicative factor 1; otherwise factor is integer value of R2 .

Resulting value = factor(L1) * (int(L2) + int(R1)) * factor(R2).

Return the expression string with parentheses inserted that yields the minimum possible value. If multiple answers tie, return any one.

Example: input "435+122" could become something like "4(35+12)2" (not necessarily optimal).

Insert parentheses to minimize expression value

Quick Overview

Comments (0)