C# Commented 46ms


  • 0
    L
       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);
            }
        }

Log in to reply
 

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