Arithmetic solution in Python


  • 0
    L

    There are a couple of helper functions:

    h(n, m) computes the order number of n in the lexicographical set of numbers with up-to-m digits.
    kth(k, m) computes the k-th number in the lexicographical set of numbers with up-to-m digits.

    The logic is to compare k with h(n, m) where m is the number of digits of n. If k is below h(n, m) the answer is kth(k, m). Otherwise the answer can be computed from the m-1 digit numbers as kth(k - t + h(n//10, m-1), m-1).

    class Solution(object):
        def findKthNumber(self, n, k):
            from math import log10
            # Sum, of digits of n
            def sumdig(n):
                return 0 if n==0 else n%10 + sumdig(n//10)
            # The order number of n in the lexicographical set of up-to-m-digit numbers
            def h(n, m): return (10*n - sumdig(n) - 10**m + 1)//9 + m
    
            # k-th number in the lexicographical set of up-to-m-digit numbers
            def kth(k, m):
                # First digit is 1 through 9
                G = (10**m - 1) // 9
                x = 1 + (k - 1) // G
                k = (k - 1) % G
                while k != 0:
                    # Subsequent digits are 0 through 9
                    # k==0 means that there are no more digits
                    G = (G - 1) // 10
                    x = 10 * x + (k - 1) // G
                    k = (k - 1) % G
                return x
    
            # The number of digits of n.
            m = 1 + int(log10(n))
            
            # The order number of n among up-to-m-digit numbers.
            t = h(n, m)
            # if k is below t get the answer
            if k <= t: return kth(k, m)
            # if k is above t look for the answer in the set of m-1 digit numbers.
            return kth(k - t + h(n//10, m-1), m-1)
    

Log in to reply
 

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