# C++ 3ms solution using stack

• Test the prefix of the answer each time. If the total number of current prefix is less than `k`, test the next prefix with `current prefix +1`, otherwise test longer prefix with `current prefix * 10`

``````class Solution {
public:
int findKthNumber(int n, int k) {
stack<int> stk;
stk.push(1);

while(k){
if(k == 1) return stk.top();
long long top = stk.top(), x = top;
stk.pop();
long long sum = 0, mask = 1;

while(top <= n){
else sum += n - top + 1;
top *= 10;
}

if(k > sum){
k -= sum;
stk.push(x+1);
}else{
k --;
stk.push(x*10);
}
}
return stk.top();
}
};``````

• Great solution. Thanks a lot. Actually, stack is not necessary. One variable is enough.

``````class Solution {
public:
int findKthNumber(int n, int k) {
int cur = 1;
while(k > 0) {
if(1 == k) return cur;
int sum = calc(n, cur);
if(k > sum) {
k -= sum;
cur = cur + 1;
}
else {
k --;
cur = cur * 10;
}
}
return cur;
}
int calc(int n, int64_t x) {
int ans = 0, t = 1;
while(x <= n) {
if(x + t - 1 <= n) ans += t;
else ans += n - x + 1;
x *= 10;
t *= 10;
}
return ans;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.