diff options
Diffstat (limited to 'kth_smallest_lexicographical.c')
-rw-r--r-- | kth_smallest_lexicographical.c | 41 |
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() { |