diff options
author | Jack Sangdahl <[email protected]> | 2025-10-01 09:45:51 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-10-01 09:45:51 -0600 |
commit | 01585d45e77abeb96336aac00896b11ad0298956 (patch) | |
tree | 13040ddfcb5ebc6cbc003af5c502b36ccc2610bf /minimize_result_add_parentheses.c | |
parent | 9885ede0c5c6394f0196b2e7d459105d77749c07 (diff) | |
download | leetcode-01585d45e77abeb96336aac00896b11ad0298956.tar.gz leetcode-01585d45e77abeb96336aac00896b11ad0298956.zip |
2232. minimise result by addding parenthesese to expression
Diffstat (limited to 'minimize_result_add_parentheses.c')
-rw-r--r-- | minimize_result_add_parentheses.c | 78 |
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) +} |