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.

It's a complete (not full) denary tree. The BFS result is normal order and the DFS result is lexicographical order.
No need to run DFS because there isand all other children are full.

 public class Solution {  
   public int findKthNumber(int n, int k) {  
     String prefix = "";  
     while(k != 0){  
       //find each digit for nth number from most significant to least significant  
       //each digit range from 0 to 9  
       int i = 0;   
       for(;i <= 9; i++){  
         //we count numbers in the same tree, when count is bigger than n for the first time  
         //we found the digit   
         int count = countPrefix(n,prefix+i);  
         if(count < k){  
           k -= count;  
         }else{  
           break;  
         }  
       }  
       prefix = prefix + i;  
       k--;  
     }  
     return Integer.valueOf(prefix);  
   }  
   public int countPrefix(int n, String prefix){  
     long a = Long.valueOf(prefix);  
     if(a == 0||a>n) return 0;  
     long b = a + 1;  
     int count = 1;//a   
     a*=10;b*=10;// next level  
     while(a <= n){  
       count += Math.min(n+1,b) - a;  
       a*=10;b*=10;// next level    
     }  
     return count;  
   }  
 }