package com.fishercoder.solutions;

/**
 * 440. K-th Smallest in Lexicographical Order
 *
 * 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.
 */
public class _440 {

    /**credit: https://discuss.leetcode.com/topic/64624/concise-easy-to-understand-java-5ms-solution-with-explaination/2*/
    public int findKthNumber(int n, int k) {
        int curr = 1;
        k = k - 1;
        while (k > 0) {
            int steps = calSteps(n, curr, curr + 1);
            if (steps <= k) {
                curr += 1;
                k -= steps;
            } else {
                curr *= 10;
                k -= 1;
            }
        }
        return curr;
    }

    //use long in case of overflow
    public int calSteps(int n, long n1, long n2) {
        int steps = 0;
        while (n1 <= n) {
            steps += Math.min(n + 1, n2) - n1;
            n1 *= 10;
            n2 *= 10;
        }
        return steps;
    }

}

@@ -414,19 +414,71 @@
  %7B%0A%0A    
-/**
+public static class Solution1 %7B%0A        /**%0A         * 
 credit: 
@@ -586,15 +586,29 @@
 on/2
+%0A         
 */%0A    
+ 
+   
 publ
@@ -648,24 +648,28 @@
 ) %7B%0A        
+    
 int curr = 1
@@ -666,24 +666,28 @@
 t curr = 1;%0A
+    
         k = 
@@ -697,24 +697,28 @@
  1;%0A        
+    
 while (k %3E 0
@@ -717,24 +717,28 @@
 e (k %3E 0) %7B%0A
+    
             
@@ -790,16 +790,20 @@
         
+  
+  
 if (step
@@ -808,24 +808,28 @@
 eps %3C= k) %7B%0A
+    
             
@@ -855,24 +855,28 @@
             
+    
 k -= steps;%0A
@@ -887,16 +887,20 @@
         
+ 
+   
 %7D else %7B
@@ -900,16 +900,20 @@
  else %7B%0A
+    
         
@@ -952,16 +952,20 @@
     
+   
+ 
 k -= 1;%0A
     
@@ -956,24 +956,28 @@
     k -= 1;%0A
+    
             
@@ -982,34 +982,40 @@
   %7D%0A        
-%7D%0A
+    %7D%0A  
         
 return curr;
@@ -998,24 +998,26 @@
 %7D%0A          
+  
 return curr;
@@ -1021,19 +1021,27 @@
 rr;%0A    
-%7D%0A%0A
+    %7D%0A%0A    
     //us
@@ -1067,16 +1067,20 @@
 verflow%0A
+    
     publ
@@ -1122,32 +1122,36 @@
 g n2) %7B%0A        
+    
 int steps = 0;%0A 
@@ -1153,24 +1153,28 @@
  0;%0A        
+   
+ 
 while (n1 %3C=
@@ -1175,24 +1175,28 @@
 (n1 %3C= n) %7B%0A
+    
             
@@ -1242,16 +1242,20 @@
         
+    
 n1 *= 10
@@ -1268,16 +1268,20 @@
         
+ 
+   
 n2 *= 10
@@ -1290,26 +1290,33 @@
         
-%7D%0A
+    %7D%0A   
         
 return s
@@ -1303,24 +1303,25 @@
 %0A           
+ 
 return steps
@@ -1326,13 +1326,22 @@
 ps;%0A    
+    %7D%0A    
 %7D
-%0A
 %0A%7D%0A

refactor 440