aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-10-01 09:45:51 -0600
committerJack Sangdahl <[email protected]>2025-10-01 09:45:51 -0600
commit01585d45e77abeb96336aac00896b11ad0298956 (patch)
tree13040ddfcb5ebc6cbc003af5c502b36ccc2610bf
parent9885ede0c5c6394f0196b2e7d459105d77749c07 (diff)
downloadleetcode-01585d45e77abeb96336aac00896b11ad0298956.tar.gz
leetcode-01585d45e77abeb96336aac00896b11ad0298956.zip
2232. minimise result by addding parenthesese to expression
-rw-r--r--minimize_result_add_parentheses.c78
-rw-r--r--minimize_result_add_parentheses.py33
2 files changed, 111 insertions, 0 deletions
diff --git a/minimize_result_add_parentheses.c b/minimize_result_add_parentheses.c
new file mode 100644
index 0000000..a338bc0
--- /dev/null
+++ b/minimize_result_add_parentheses.c
@@ -0,0 +1,78 @@
+// 2232. Minimize Result by Adding Parentheses to Expression
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed string 'expression' of the form 'num1+num2' where
+ * 'num1' and 'num2' represent 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 multiple answers that yield the same result, return any of
+ * them.
+ */
+
+void helper(char *res, char *expression, int n, int pos) {
+ int num = INT_MAX, l = 0, r = 0;
+ for (int i = 0; i < pos; i++) {
+ int lidx = i, a = 0, c = 0;
+ for (int j = lidx; j < pos; j++) {
+ a *= 10;
+ a += (expression[j] - '0');
+ }
+ for (int j = 0; j < lidx; j++) {
+ c *= 10;
+ c += (expression[j] - '0');
+ }
+ if (!c)
+ c++;
+ for (int j = n - 1; j > pos; j--) {
+ int ridx = j, b = 0, d = 0;
+ for (int k = ridx; k > pos; k--)
+ b += (expression[k] - '0') * pow(10, ridx - k);
+ for (int k = ridx + 1; k < n; k++) {
+ d *= 10;
+ d += (expression[k] - '0');
+ }
+ if (!d)
+ d++;
+ int ans = c * (a + b) * d;
+ if (ans < num) {
+ num = ans;
+ l = lidx;
+ r = ridx;
+ }
+ }
+ }
+ int idx = 0;
+ for (int i = 0; i < n + 3; i++) {
+ if (i == l)
+ res[i] = '(';
+ else if (i == r + 2)
+ res[i] = ')';
+ else
+ res[i] = expression[idx++];
+ }
+}
+
+char *minimizeResult(char *expression) {
+ int n = strlen(expression), pos = 0;
+ for (int i = 0; i < n; i++)
+ if (expression[i] == '+') {
+ pos = i;
+ break;
+ }
+ char *ans = (char *)calloc(n + 3, sizeof(char));
+ helper(ans, expression, n, pos);
+ return ans;
+}
+
+int main() {
+ char *e1 = "247+38", *mr1 = minimizeResult(e1);
+ char *e2 = "12+34", *mr2 = minimizeResult(e2);
+ char *e3 = "999+999", *mr3 = minimizeResult(e3);
+ printf("%s\n", mr1); // expect: 2(47+38)
+ printf("%s\n", mr2); // expect: 1(2+3)4
+ printf("%s\n", mr3); // expect: (999+999)
+}
diff --git a/minimize_result_add_parentheses.py b/minimize_result_add_parentheses.py
new file mode 100644
index 0000000..b59eca3
--- /dev/null
+++ b/minimize_result_add_parentheses.py
@@ -0,0 +1,33 @@
+# 2232. Minimize Result by Adding Parentheses to Expression
+
+"""
+you are given a 0-indexed string 'expression' of the form 'num1+num2' where
+'num1' and 'num2' represent 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 multiple answers that yield the same result, return any of
+them.
+"""
+
+
+class Solution(object):
+ def minimizeResult(self, expression):
+ """
+ :type expression: str
+ :rtype: str
+ """
+ left, right = expression.split("+")
+ value = lambda s: eval(s.replace("(", "*(").replace(")", ")*").strip("*"))
+ l = [left[0:i] + "(" + left[i:] for i in range(len(left))]
+ r = [right[0:i] + ")" + right[i:] for i in range(1, len(right) + 1)]
+ return min([i + "+" + j for i in l for j in r], key=value)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minimizeResult(expression="247+38"))
+ print(obj.minimizeResult(expression="12+34"))
+ print(obj.minimizeResult(expression="999+999"))