440. K-th Smallest in Lexicographical Order

https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/

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.

---

	class Solution {
	public int findKthNumber(int n, int k) {
	int ans = 0;
	k -= 1;
	int curr = 1;
	while (k > 0) {
	// steps to move to sibling at same level
	int steps = findSteps(n, curr, curr + 1);
	if (steps <= k) {
	k-= steps;
	curr += 1;
	} else {
	// traverse one level deep
	k -=1;
	curr *= 10;
	}
	}
	return curr;
	}
	// steps to move to sibling at same level
	private int findSteps(int n, long n1, long n2) {
	int steps = 0;
	while (n1 <= n) {
	steps += Math.min(n + 1, n2) - n1;
	n1 *= 10;
	n2 *= 10;
	}
	return steps;
	}
	}

view raw 440.KthSmallestInLexicographicalOrder.java hosted with ❤ by GitHub