aboutsummaryrefslogtreecommitdiff
path: root/minimize_result_add_parentheses.c
diff options
context:
space:
mode:
Diffstat (limited to 'minimize_result_add_parentheses.c')
-rw-r--r--minimize_result_add_parentheses.c78
1 files changed, 78 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)
+}