Formatted question description: https://leetcode.ca/all/440.html

440. K-th Smallest in Lexicographical Order

Level

Hard

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.

Solution

Starting from 1, let curr be the current prefix, and the next prefix is curr + 1. Count the number of integers with prefix curr. If the number of integers with prefix curr is greater than k, then set curr = curr * 10 and use the updated curr to calculate the next prefix curr + 1. Otherwise, subtract the number of integers from k, and set curr = curr + 1. Repeat the process until k becomes 0. Finally, return curr.

  • class Solution {
        public int findKthNumber(int n, int k) {
            int curr = 1;
            k--;
            while (k > 0) {
                int steps = getSteps(n, curr, curr + 1);
                if (steps > k) {
                    curr *= 10;
                    k--;
                } else {
                    curr++;
                    k -= steps;
                }
            }
            return curr;
        }
    
        public int getSteps(int n, long curr, long next) {
            int steps = 0;
            while (curr <= n) {
                steps += Math.min(n + 1, next) - curr;
                curr *= 10;
                next *= 10;
            }
            return steps;
        }
    }
    
  • Todo
    
  • class Solution(object):
      # naive pre-order traversal on denary tree
      def _findKthNumber(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
    
        def dfs(cur, n):
          if self.k == 0:
            return cur
          self.k -= 1
          if cur == 0:
            for i in range(1, 10):
              if i > n:
                break
              ret = dfs(i, n)
              if ret:
                return ret
          else:
            for i in range(0, 10):
              if cur * 10 + i > n:
                break
              ret = dfs(cur * 10 + i, n)
              if ret:
                return ret
    
        self.k = k
        return dfs(0, n)
    
      # optimized solution
      def findKthNumber(self, n, k):
        def getGap(n, ans):
          gap = 0
          start = ans
          end = start + 1
          while start <= n:
            gap += max(0, min(n + 1, end) - start)
            start *= 10
            end *= 10
          return gap
    
        ans = 1
        k -= 1
        while k > 0:
          gap = getGap(n, ans)
          if gap <= k:
            ans += 1
            k -= gap
          else:
            ans *= 10
            k -= 1
        return ans
    
    

All Problems

All Solutions