# Concise nonrecursive c++ 0ms solution

• ``````// The basic idea is to put numbers in 3 categories: before, after, or equal.
// The category checking  can be optimized as only "equal" can change to "before" or "after".
// Once is in "before" or "after", it will stay in that category.
class Solution {
public:
int findKthNumber(int n, int k) {

string res;
string nstr = to_string(n);

int dCounter = 0;
for (int i = 0; i<nstr.length(); i++)
dCounter += pow(10,i);

int pos = 0;
int hist[57+1] = {};

while (k>0)
{
k--; //tricky, skip the current number

if ( res==nstr.substr(0,pos) )
{
int sum = 0;
hist[nstr[pos]] = 0;
for (char d = res.empty()?'1':'0'; d <= '9'; d++)
{
if (d< nstr[pos]) hist[d] = dCounter;
else if ( d>nstr[pos] )  hist[d] = dCounter / 10;
sum += hist[d];
}
n -= sum;
hist[nstr[pos]] =n;
n--; //exclude the current number
}
else if ( res<nstr.substr(0, pos) )
{
for (char d = '0'; d <= '9'; d++)
hist[d] = dCounter;
}
else
{
for (char d = '0'; d <= '9'; d++)
hist[d] = dCounter/10;
}

char d = '0';
while (k>=hist[d]) k -= hist[d++];

res.append(1, d);

pos++;
dCounter /= 10;

}

return atoi(res.c_str());
}
};
``````

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