aboutsummaryrefslogtreecommitdiff
path: root/kth_smallest_lexicographical.c
diff options
context:
space:
mode:
Diffstat (limited to 'kth_smallest_lexicographical.c')
-rw-r--r--kth_smallest_lexicographical.c41
1 files changed, 20 insertions, 21 deletions
diff --git a/kth_smallest_lexicographical.c b/kth_smallest_lexicographical.c
index 85551db..3567a1f 100644
--- a/kth_smallest_lexicographical.c
+++ b/kth_smallest_lexicographical.c
@@ -1,34 +1,33 @@
// 440. K-th Smallest in Lexicographical Order
-#include <math.h>
-#include <stdio.h>
-#include <stdlib.h>
+#include "leetcode.h"
// given two integers 'n' and 'k', return the k'th lexicographically smallest
// integer
-int count_prefix(int n, long long prefix) {
- long long offset = 10, target = n;
- int total = 0;
- for (int i = 1; i <= 9; i++) {
- long long min = prefix * offset;
- long long max = min + offset - 1;
- if (target < min)
- break;
- total += fmin(target, max) - min + 1;
+long long count_step(long long prefix, long long n) {
+ long long curr = prefix, next = prefix + 1, steps = 0;
+ while (curr <= n) {
+ steps += (next <= n) ? next - curr : n - curr + 1;
+ curr *= 10;
+ next *= 10;
}
- return total + 1;
+ return steps;
}
int findKthNumber(int n, int k) {
- int prefix = 0;
- if (k)
- for (int i = !prefix ? 1 : 0; i <= 9; i++) {
- int prefix_cnt = count_prefix(n, 10 * prefix + i);
- if (k <= prefix_cnt)
- return findKthNumber(n, k - 1);
- k -= prefix_cnt;
+ int curr = 1;
+ k--;
+ while (k) {
+ long long steps = count_step(curr, n);
+ if (steps <= k) {
+ curr++;
+ k -= steps;
+ } else {
+ curr *= 10;
+ k--;
}
- return prefix;
+ }
+ return curr;
}
int main() {