440. Lexicographical small number K: Numerical simulation exercises

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

This is 440 on LeetCode, the KTH digit in lexicographical order. Difficulty is difficult.

Tag: “Math”, “simulation”, “finding patterns”, “counting”

Given integers NNN and KKK, return the lexicographically ordered KKK smallest number in [1,n][1, n].

Example 1:

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.Copy the code

Example 2:

Input: n = 1, k = 1 Output: 1Copy the code

Tip:

• 
  $1 <= k <= n <= 10^9$

Count analog

Look for the number with the smallest KKK in dictionary order.

We can do this in two steps: “Determine the prefix” and “find the target value starting with a prefix”.

Suppose we have a function int getCnt(int x, int limit) that implements the number of numbers in the range [1,limit][1, limit] prefixed with XXX.

With this function, we can enumerate from the smallest prefix 111, assuming the current enumeration to the prefix XXX, according to the size relationship between CNT =getCnt(x,n) CNT =getCnt(x,n) CNT =getCnt(x,n) and KKK:

• CNT < KCNT < KCNT
• CNT ⩾ KCNT \geqslant KCNT ⩾ K: indicates that the target value prefix must be XXX, and we need to search for target value if XXX is the prefix. At this point, multiply XXX by 101010, and KKK minus 111 (which means XXX itself is skipped). Find the target value from the next “lexicographic order greater than XXX” prefix.

When k=1k =1k =1, the current prefix XXX is the answer (meaning XXX itself is the smallest of all numbers prefixed with XXX).

Int getCnt(int x, int limit)

For convenience, remember the number of digits of XXX as NNN and the number of limitLimitLimit as MMM.

According to the function definition of getCnt, within the range [1,limit][1, limit][1,limit], the number of values prefixed with XXX is equal to the sum of all the following cases:

• Numbers with the number of digits NNN: only XXX itself, 111 in total;
• Figures for
  $n + 1 < m$The number, there isx0 到 x9, a total of
  $10$A;
• Figures for
  $n + 2 < m$The number, there isx00 到 x99, a total of
  $100$A;
• .
• Figures for
  $m$According to”
  $limit$Length and the
  $x$Equivalent prefix
  $u$“And”
  $x$“The size of the relationship, further points to discuss (for example 🌰, when
  $limit = 12456$.
  $x$ 为
  $123$When,
  $u = 124$And the digits are different
  $k = 2$A) :
  • U
  • U ==xu ==xu ==x: In this case, some of the numbers whose bits are MMM meet the limitLimitLimit limit, and the legal number is limit−x∗ 10K +1limit -x * 10^k + 1Limit −x∗ 10K +1;
  • U >xu > Xu >x: The number of bits MMM is less than limitLimitLimit. The legal number is 10k10^ k10K.

Code:

class Solution {
    public int findKthNumber(int n, int k) {
        int ans = 1;
        while (k > 1) {
            int cnt = getCnt(ans, n);
            if (cnt < k) {
                k -= cnt; ans++;
            } else {
                k--; ans *= 10; }}return ans;
    }
    int getCnt(int x, int limit) {
        String a = String.valueOf(x), b = String.valueOf(limit);
        int n = a.length(), m = b.length(), k = m - n;
        int ans = 0, u = Integer.parseInt(b.substring(0, n));
        for (int i = 0; i < k; i++) ans += Math.pow(10, i);
        if (u > x) ans += Math.pow(10, k);
        else if (u == x) ans += limit - x * Math.pow(10, k) + 1;
        returnans; }}Copy the code

• Time complexity: Enumerating prefixes as wellgetCntThe operations are all bit dependent and the complexity is
  $O(\log{n})$. The overall complexity is
  $O(\log{^2}{n})$
• Space complexity: ignore the substring generation complexity of O(1)O(1)O(1), otherwise O(log⁡2n)O(\log{^2}{n})O(log2n)

The last

This is the No.440 article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode by the start date, some of which have lock questions.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.