Arithmetic solution in Python

• 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)
``````

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