K-th Smallest in Lexicographical Order in C++

Suppose we have two values n and k. We have to find the lexicographically kth smallest integer in the range of 1 to n. So if the input is like n = 14 and k = 3, then the output will be 11, as the sequence will be [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9], then the kth number is 11.

To solve this, we will follow these steps −

• Define a function findKthNumber(), this will take n, k,
• curr := 1
• (decrease k by 1)
• while k is non-zero, do −
  • steps := call the function calcSteps(n, curr, curr + 1)
  • if steps <= k, then −
    • k := k - steps
    • (increase curr by 1)
  • Otherwise
    • curr := curr * 10
    • k := k - 1
  • return curr
• Define a function calcSteps(), this will take nax, n1, n2,
• ret := 0
• while n1 <= nax, do −
  • ret := ret + minimum of nax + 1 and n2 – n1
  • n1 := n1 * 10
  • n2 := n2 * 10
• return ret

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public:    int findKthNumber(int n, int k) {       int curr = 1;       k--;       while(k){          int steps = calcSteps(n, curr, curr + 1);          if(steps <= k){             k -= steps;             curr++;          }else{             curr *= 10;             k -= 1;          }       }       return curr;    }    int calcSteps(lli nax, lli n1, lli n2){       int ret = 0;       while(n1 <= nax){          ret += min(nax + 1, n2) - n1;          n1 *= 10;          n2 *= 10;       }       return ret;    } }; main(){    Solution ob;    cout << (ob.findKthNumber(14,3)); }

Input

14,3

Output

11