aboutsummaryrefslogtreecommitdiff
path: root/minimize_result_add_parentheses.c
blob: a338bc0b518c2c44dc1688a0ff979be5ddfd3bd8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
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)
}