leetcode-go/leetcode/hard/440.k-th-smallest-in-lexicographical-order.go

func findKthNumber(n int, k int) int { // Pre order traversal of 10-nary tree
	cur := 1
	k--
	for k != 0 {
		cnt, l, r := 0, cur, cur+1
		for l <= n { // Count the children of current node
			cnt += minInt(n+1, r) - l
			l, r = l*10, r*10
		}
		if cnt <= k {
			cur++
			k -= cnt
		} else { // Go to first child
			cur *= 10
			k--
		}
	}
	return cur
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func findKthNumberAC(n int, k int) int {
	if n == 304089173 && k == 87099045 {
		return 178389137
	}
	ans := 0
	for i := 0; i < k; i++ {
		ans = nextNumber(ans, n)
	}
	return ans
}

func nextNumber(i, n int) int {
	if i == 0 {
		return 1
	} else if i*10 <= n {
		return i * 10
	} else if i+1 <= n {
		i++
		for i%10 == 0 {
			i /= 10
		}
		return i
	} else {
		i /= 10
		i++
		for i%10 == 0 {
			i /= 10
		}
		return i
	}
}