440. K-th Smallest in Lexicographical Order

LeetCode 440. K-th Smallest in Lexicographical Order

Description

Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.

Note: 1 ≤ k ≤ n ≤ 109.

Example:

Input:
n: 13   k: 2

Output:
10

Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Tags

Tree

Solution

In essential, we can build a 10-ary tree to represent a set of number from 1 to n in Lexicographical Order. We can obtain the k-th number by moving a pointer cur from 1 with k-1 steps in pre-order manner. To jump over a bunch of nodes, we can check if the k-th number is belonging the child of cur. To achieve this, we calculate the number of nodes (which should not be greater than n) and compare it with k. If the number is smaller than k, we substract these nodes from k and move cur by 1 step horizontally. Otherwise, we let k-- and cur*=10, which means we dive into the next level and find the k-th number on this level. When k==0, we return cur.

Complexity

• Time complexity: $O(k)$

• Space complexity: $O(1)$

Code

func findKthNumber(n int, k int) int {
	getSteps := func(n, prefix int) (count int) {
		for cur, next := prefix, prefix+1; cur <= n; cur, next = cur*10, next*10 {
			count += min(n+1, next) - cur
		}
		return
	}
	cur, k := 1, k-1 // skip 0
	for k > 0 {
		steps := getSteps(n, cur)
		if k >= steps { // right
			k -= steps
			cur++
		} else { // down
			k--
			cur *= 10
		}
	}
	return cur
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Reference

1. 十叉树