leetcode

commit d3382a11112d2dfe31b2d156c73d07d1ee213a97
parent 38025a19a342cb266e766e8cf9aeadfccd8c68ae
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat,  7 Jun 2025 20:53:32 -0600

386. lexicographical numbers

Diffstat:
M
lexicographical_numbers.c
 | 
33
++++++++++++++-------------------

1 file changed, 14 insertions(+), 19 deletions(-)
diff --git a/lexicographical_numbers.c b/lexicographical_numbers.c
@@ -7,27 +7,22 @@
  * complexity and uses O(1) extra space.
  */
 
-void lex(int *res, int n, int i, int digit, int *k) {
-  if (!digit)
-    return;
-  for (int j = i * 10; j < (i + 1) * 10 && j <= n; j++) {
-    res[(*k)++] = j;
-    lex(res, n, j, digit - 1, k);
-  }
-}
-
 int *lexicalOrder(int n, int *returnSize) {
-  int *ans = (int *)malloc((n + 1) * sizeof(int));
-  int tmp = n, max_digit = 0, k = 0;
-  while (tmp) {
-    tmp /= 10;
-    max_digit++;
-  }
-  for (int i = 1; i < 10 && i <= n; i++) {
-    ans[k++] = i;
-    lex(ans, n, i, max_digit, &k);
+  int *ans = (int *)malloc(n * sizeof(int));
+  int curr = 1, k = 0;
+  for (int i = 0; i < n; i++) {
+    ans[i] = curr;
+    if (((curr << 3) + (curr << 1)) <= n)
+      curr = (curr << 3) + (curr << 1);
+    else {
+      if (curr >= n)
+        curr /= 10;
+      curr++;
+      while (!(curr % 10))
+        curr /= 10;
+    }
   }
-  *returnSize = k;
+  *returnSize = n;
   return ans;
 }