```
public class Solution
{
public int FindKthNumber(int n, int k)
{
if (n < 10) return k;
int ret = 0;
//10 buckets, 9 buckets are used on the first pass as there is no "0" bucket initially.
int[] buckets = new int[10]; /
bool isFirst = true;
while (k > 0)
{
//obtain the count of digits in each bucket.
GenerateBuckets(n, buckets, isFirst);
//determine which bucket k lies in, this index is the next digit of the return value.
int bucketIndex = FindIndex(k, buckets);
ret = ret * 10 + bucketIndex + (isFirst ? 1 : 0); //add the next digit
//k and n need to be modified for the next round.
k -= (ElementsBefore(bucketIndex, buckets) + 1);
n = buckets[bucketIndex] - 1;
isFirst = false;
}
return ret;
}
private static void GenerateBuckets(int n, int[] buckets, bool isFirst)
{
int iterations = isFirst ? 9 : 10;
int maxValue = ObtainMaxBucketSize(n); //the max value in a bucket is a repetition of 1's (for example, 111)
int minValue = maxValue - (int)Math.Pow(10, (int)Math.Log10(n)); //the min value of a bucket is the maxValue with 1 less 1 (example: 11).
//Note: the minValue may be 0.
for (int i = 0; i < iterations; i++)
buckets[i] = minValue;
int remaining = n - minValue * iterations; //we have handled minValue * iterations elements, determine how many are left.
int maxAddition = maxValue - minValue; //A power of 10, the most we can add to a single bucket.
for (int i = 0; i < iterations; i++)
{
buckets[i] += Math.Max(0, Math.Min(remaining, maxAddition));
remaining -= maxAddition;
if (remaining <= 0) break;
}
}
/// <summary>The number of elements before the given bucket index.</summary>
private int ElementsBefore(int index, int[] buckets)
=> (from i in Enumerable.Range(0, index) select buckets[i]).Sum();
/// <summary>Determines the index of the bucket in which k lies.</summary>
private int FindIndex(int k, int[] buckets)
{
int high = 0;
for(int i = 0; i < buckets.Length; i++)
{
high += buckets[i];
if (k <= high) return i;
}
throw new InvalidOperationException();
}
private static int ObtainMaxBucketSize(int n)
=> obtainOnes(numberOfOnes: (int)Math.Log10(n) + 1);
/// <summary>Recurrence returning an integer containing "n+1" ones: 1, 11, 111</summary>
private static int obtainOnes(int numberOfOnes)
{
if (numberOfOnes == 1) return 1;
int pow10 = (int)Math.Pow(10, numberOfOnes - 1);
return pow10 + obtainOnes(numberOfOnes-1);
}
}
```