diff options
author | Jack Sangdahl <[email protected]> | 2024-09-21 21:44:03 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-21 21:44:03 -0600 |
commit | b4a3151742e580f176f60af0815e95fa3066a5f1 (patch) | |
tree | 318d8875d89037c6e6a24547c1fe066685970fb3 | |
parent | e1681d1ad79dd6a2961fe04d24c1ed2152da161a (diff) | |
download | leetcode-b4a3151742e580f176f60af0815e95fa3066a5f1.tar.gz leetcode-b4a3151742e580f176f60af0815e95fa3066a5f1.zip |
440. kth smallest in lexicographical order
-rw-r--r-- | kth_smallest_lexicographical.c | 41 | ||||
-rw-r--r-- | kth_smallest_lexicographical.cpp | 48 | ||||
-rw-r--r-- | kth_smallest_lexicographical.py | 36 |
3 files changed, 74 insertions, 51 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() { diff --git a/kth_smallest_lexicographical.cpp b/kth_smallest_lexicographical.cpp index 1e292ec..71478e9 100644 --- a/kth_smallest_lexicographical.cpp +++ b/kth_smallest_lexicographical.cpp @@ -1,43 +1,31 @@ +// 440. K-th Smallest in Lexicographical Order #include "leetcode.h" +// given two integers 'n' and 'k', return the k'th lexicographically smallest +// integer class Soltuion { public: int findKthNumber(int n, int k) { - int ans = 0, rankNum = 0, next = 0, rankNext = 0; - while (rankNum != k) { - int lower = ans ? 0 : 1, upper = 9; - while (lower < upper) { - auto mid = (lower + upper + 1) / 2; - next = ans * 10 + mid; - rankNext = rank(next, n); + int curr = 1; + for (--k; k > 0;) { + int cnt = 0; + for (long long first = static_cast<long long>(curr), last = first + 1; + first <= n; first *= 10, last *= 10) + cnt += static_cast<int>((min(n + 1LL, last) - first)); + if (k >= cnt) { + ++curr; + k -= cnt; + } else { + curr *= 10; + --k; } - ans *= 10, ans += lower; - rankNum = (ans == next ? rankNext : rank(ans, n)); } - return ans; - } - -private: - static int rank(int prefix, int maxVal) { - int ret = 1, num = 0; - for (int i = prefix; i; i /= 10, ++num) - for (int j = 1; j <= i % 10; ++j) - ret += numPrefixes(i - j, maxVal); - ret += num - 1; - return ret; - } - static int numPrefixes(int prefix, int maxVal) { - if (prefix == 0) - return 0; - int ret = 0; - unsigned long long ull = 1; - for (unsigned long long val = prefix; val <= maxVal; ull *= 10, val *= 10) - ret += min(ull, maxVal - val + 1); - return ret; + return curr; } }; int main() { Soltuion obj; - cout << obj.findKthNumber(13, 2); + printf("%d\n", obj.findKthNumber(13, 2)); // expect: 10 + printf("%d\n", obj.findKthNumber(1, 1)); // expect: 1 } diff --git a/kth_smallest_lexicographical.py b/kth_smallest_lexicographical.py new file mode 100644 index 0000000..8f56678 --- /dev/null +++ b/kth_smallest_lexicographical.py @@ -0,0 +1,36 @@ +# 440. K-th Smallest in Lexicographical Order + +""" +given two integers 'n' and 'k', return the k'th lexicographically smallest +integer +""" + + +class Solution(object): + def findKthNumber(self, n, k): + """ + :type n: int + :type k: int + :rtype: int + """ + curr = 1 + k -= 1 + while k > 0: + cnt = 0 + interval = [curr, curr + 1] + while interval[0] <= n: + cnt += min(n + 1, interval[1]) - interval[0] + interval = [10 * interval[0], 10 * interval[1]] + if k >= cnt: + curr += 1 + k -= cnt + else: + curr *= 10 + k -= 1 + return curr + + +if __name__ == "__main__": + obj = Solution() + print(obj.findKthNumber(13, 2)) + print(obj.findKthNumber(1, 1)) |