aboutsummaryrefslogtreecommitdiff
path: root/montone_increasing_digit.c
diff options
context:
space:
mode:
Diffstat (limited to 'montone_increasing_digit.c')
-rw-r--r--montone_increasing_digit.c53
1 files changed, 53 insertions, 0 deletions
diff --git a/montone_increasing_digit.c b/montone_increasing_digit.c
new file mode 100644
index 0000000..843db35
--- /dev/null
+++ b/montone_increasing_digit.c
@@ -0,0 +1,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
+}