Minimum factorization

Math Greedy

33.9% acceptance

Mar 31, 2026

133

112

Given a positive integer num, return the smallest positive integer x whose multiplication of each digit equals num. If there is no answer or the answer is not fit in 32-bit signed integer, return 0.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_factorization(num: i32) -> i32 {
    if num == 1 {
      return 1;
    }
    let mut n = num as i64;
    let mut digits = Vec::new();
    for d in (2..=9).rev() {
      while n % d == 0 {
        digits.push(d);
        n /= d;
      }
    }
    if n != 1 {
      return 0;
    }
    digits.reverse();
    let mut result: i64 = 0;
    for &d in &digits {
      result = result * 10 + d;
      if result > i32::MAX as i64 {
        return 0;
      }
    }
    result as i32
  }
}