1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include "leetcode.h"
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);
}
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;
}
};
int main() {
Soltuion obj;
cout << obj.findKthNumber(13, 2);
}
|