440. K-th Smallest in Lexicographical Order

Description

Here

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.

Solution

Reference

Code

  public int findKthNumber(int n, int k) {
    int cur = 1;
    k--;
    while (k > 0) {
      final int step = calculateSteps(n, cur, cur + 1);
      if (step <= k) {
        cur++;
        k -= step;
      } else {
        k--;
        cur *= 10;
      }
    }
    return cur;
  }

  /**
   * Calculate the steps that needs from <tt>cur</tt>(inclusive) to <tt>cur + 1</tt> (exclusive)
   *
   * @param n
   * @param cur
   * @param curPlus1
   * @return
   */
  private static int calculateSteps(int n, long cur, long curPlus1) {
    int steps = 0;
    while (cur <= n) {
      if (curPlus1 <= n) {
        steps += curPlus1 - cur;
      } else {
        steps += n - cur + 1;
      }
      curPlus1 *= 10;
      cur *= 10;
    }
    return steps;
  }