Balanced k factor decomposition

Math Backtracking Number Theory

40.0% acceptance

Feb 25, 2026

120

Given two integers n and k, split the number n into exactly k positive integers such that the product of these integers is equal to n. Return any one split in which the maximum difference between any two numbers is minimized. You may return the result in any order.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_difference(n: i32, k: i32) -> Vec<i32> {
    let k = k as usize;
    let mut best: Option<Vec<i32>> = None;
    let mut best_diff = i32::MAX;

    // Enumerate factor multisets in non-decreasing order (min_d = lower bound for next factor).
    // At k==1 the remaining quotient n must be >= min_d to avoid duplicates.
    fn solve(
      n: i32,
      k: usize,
      min_d: i32,
      factors: &mut Vec<i32>,
      best: &mut Option<Vec<i32>>,
      best_diff: &mut i32,
    ) {
      if *best_diff == 0 {
        return;
      }
      if k == 1 {
        if n >= min_d {
          factors.push(n);
          // factors are in non-decreasing order, so first is min and last is max
          let diff = factors.last().unwrap() - factors.first().unwrap();
          if diff < *best_diff {
            *best_diff = diff;
            *best = Some(factors.clone());
          }
          factors.pop();
        }
        return;
      }
      let mut i = min_d;
      while i * i <= n {
        if n % i == 0 {
          factors.push(i);
          solve(n / i, k - 1, i, factors, best, best_diff);
          factors.pop();
          if *best_diff == 0 {
            return;
          }
        }
        i += 1;
      }
    }

    let mut factors = Vec::new();
    solve(n, k, 1, &mut factors, &mut best, &mut best_diff);
    best.unwrap_or_default()
  }
}