aboutsummaryrefslogtreecommitdiff
path: root/kth_smallest_lexicographical.cpp
blob: 71478e912255a00e624b75af4e952c6a5413737a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 440. K-th Smallest in Lexicographical Order
#include "leetcode.h"
// given two integers 'n' and 'k', return the k'th lexicographically smallest
// integer

class Soltuion {
public:
  int findKthNumber(int n, int k) {
    int curr = 1;
    for (--k; k > 0;) {
      int cnt = 0;
      for (long long first = static_cast<long long>(curr), last = first + 1;
           first <= n; first *= 10, last *= 10)
        cnt += static_cast<int>((min(n + 1LL, last) - first));
      if (k >= cnt) {
        ++curr;
        k -= cnt;
      } else {
        curr *= 10;
        --k;
      }
    }
    return curr;
  }
};

int main() {
  Soltuion obj;
  printf("%d\n", obj.findKthNumber(13, 2)); // expect: 10
  printf("%d\n", obj.findKthNumber(1, 1));  // expect: 1
}