Welcome to Subscribe On Youtube

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;
        }
    }
    
  • class Solution:
        def findKthNumber(self, n: int, k: int) -> int:
            def count(curr):
                next, cnt = curr + 1, 0
                while curr <= n:
                    cnt += min(n - curr + 1, next - curr)
                    next, curr = next * 10, curr * 10
                return cnt
    
            curr = 1
            k -= 1
            while k:
                cnt = count(curr)
                if k >= cnt:
                    k -= cnt
                    curr += 1
                else:
                    k -= 1
                    curr *= 10
            return curr
    
    ############
    
    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
    
    
  • class Solution {
    public:
        int n;
    
        int findKthNumber(int n, int k) {
            this->n = n;
            --k;
            long long curr = 1;
            while (k) {
                int cnt = count(curr);
                if (k >= cnt) {
                    k -= cnt;
                    ++curr;
                } else {
                    --k;
                    curr *= 10;
                }
            }
            return (int) curr;
        }
    
        int count(long long curr) {
            long long next = curr + 1;
            int cnt = 0;
            while (curr <= n) {
                cnt += min(n - curr + 1, next - curr);
                next *= 10;
                curr *= 10;
            }
            return cnt;
        }
    };
    
  • func findKthNumber(n int, k int) int {
    	count := func(curr int) int {
    		next := curr + 1
    		cnt := 0
    		for curr <= n {
    			cnt += min(n-curr+1, next-curr)
    			next *= 10
    			curr *= 10
    		}
    		return cnt
    	}
    	curr := 1
    	k--
    	for k > 0 {
    		cnt := count(curr)
    		if k >= cnt {
    			k -= cnt
    			curr++
    		} else {
    			k--
    			curr *= 10
    		}
    	}
    	return curr
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions