K th smallest in lexicographical order

Trie

46.2% acceptance

Jan 13, 2026

1647

147

Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_kth_number(n: i32, k: i32) -> i32 {
    let mut curr = 1i64;
    let mut k = k - 1;
    
    while k > 0 {
      let steps = Self::count_steps(n as i64, curr, curr + 1);
      if steps <= k {
        curr += 1;
        k -= steps;
      } else {
        curr *= 10;
        k -= 1;
      }
    }
    
    curr as i32
  }
  
  fn count_steps(n: i64, mut curr: i64, mut next: i64) -> i32 {
    let mut steps = 0;
    while curr <= n {
      steps += (next.min(n + 1) - curr) as i32;
      curr *= 10;
      next *= 10;
    }
    steps
  }
}