aboutsummaryrefslogtreecommitdiff
path: root/kth_smallest_lexicographical.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'kth_smallest_lexicographical.cpp')
-rw-r--r--kth_smallest_lexicographical.cpp48
1 files changed, 18 insertions, 30 deletions
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
}