Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 22

Description

K-th Smallest in Lexicographical Order

Given two integers n and k, return the kth lexicographically smallest integer in the range [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.

Example 2:

Input: n = 1, k = 1
Output: 1

Constraints:

• 1 <= k <= n <= 109

Solution

class Solution {
  int getReqNum(long long a, long long b, int &n) {
    int gap = 0;
    while(a <= n) {
      gap += min<long long>(n + 1, b) - a;
      a *= 10;
      b *= 10;
    }
    return gap;
  }
public:
  int findKthNumber(int n, int k) {
    long long num = 1;
    for(int i = 1; i < k; ) {
      int req = getReqNum(num, num + 1, n);
      if(i + req <= k) {
        i += req;
        num += 1;
      } else {
        i += 1;
        num *= 10;
      }
    }
    return num;
  }
};