Smallest number with given digit product

Math Greedy

43.4% acceptance

Mar 31, 2026

Given a positive integer n, return a string representing the smallest positive integer such that the product of its digits is equal to n, or "-1" if no such number exists.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_number(n: i64) -> String {
    if n == 1 { return "1".to_string(); }
    let mut digits = Vec::new();
    let mut rem = n;
    for d in (2..=9).rev() {
      while rem % d == 0 {
        digits.push(d);
        rem /= d;
      }
    }
    if rem > 1 { return "-1".to_string(); }
    digits.reverse();
    digits.iter().map(|d| std::char::from_digit(*d as u32, 10).unwrap()).collect()
  }
}