aboutsummaryrefslogtreecommitdiff
path: root/montone_increasing_digit.c
blob: 843db3551e4e2c84cd2d1e54d3db334c7b1f9378 (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
// 738. Monotone Increasing Digits
#include "leetcode.h"

/*
 * an integer has monotone increasing digits if and only if each pair of
 * adjacent digts 'x' and 'y' satisfy 'x <= y'. given an integer 'n', return the
 * largest number that is less than or equal to 'n' with monotone inccreasing
 * digits
 */

char *int_to_str(int n) {
  char *res = malloc(11);
  int val = n, idx = 0;
  while (val) {
    res[idx] = val % 10 + '0';
    val /= 10;
    idx++;
  }
  res[idx] = '\0';
  for (int i = 0; i < idx / 2; i++) {
    char tmp = res[i];
    res[i] = res[idx - 1 - i];
    res[idx - 1 - i] = tmp;
  }
  return res;
}

int str_to_int(char *s) {
  int n = strlen(s), val = 0;
  for (int i = 0; i < n; i++)
    val *= 10 + s[i] - '0';
  return val;
}

int monotoneIncreasingDigits(int n) {
  char *s = int_to_str(n);
  int j = strlen(s), k = j;
  for (int i = k - 1; i; i--) {
    if (s[i] >= s[i - 1])
      continue;
    s[i - 1]--;
    j = i;
  }
  for (int i = j; i < k; i++)
    s[i] = '9';
  return str_to_int(s);
}

int main() {
  printf("%d\n", monotoneIncreasingDigits(10));   // expect: 9
  printf("%d\n", monotoneIncreasingDigits(1234)); // expect: 1234
  printf("%d\n", monotoneIncreasingDigits(332));  // expect: 299
}