Smallest divisible digit product ii

fn gcd64(a: i64, b: i64) -> i64 {
  if b == 0 { a } else { gcd64(b, a % b) }
}

/// Precompute table: dp23[i][j] = minimum digits (from {2,3,4,6,8,9}) to cover
/// at least 2^i * 3^j.  Forward BFS from (0,0): each digit extends coverage.
/// Digit contributions: 2→(1,0), 3→(0,1), 4→(2,0), 6→(1,1), 8→(3,0), 9→(0,2).
/// Single pass over the grid suffices because all contributions are non-negative:
/// every state propagated to has index ≥ current in both dimensions (with
/// clamping at a_max/b_max), so it is visited later in row-major order.
fn build_dp23(a_max: usize, b_max: usize) -> Vec<Vec<usize>> {
  const INF: usize = usize::MAX / 2;
  let mut dp = vec![vec![INF; b_max + 1]; a_max + 1];
  dp[0][0] = 0;
  for i in 0..=a_max {
    for j in 0..=b_max {
      let cur = dp[i][j];
      if cur == INF { continue; }
      for &(di, dj) in &[(1usize, 0usize), (0, 1), (2, 0), (1, 1), (3, 0), (0, 2)] {
        let ni = (i + di).min(a_max);
        let nj = (j + dj).min(b_max);
        let cost = cur + 1;
        if cost < dp[ni][nj] {
          dp[ni][nj] = cost;
        }
      }
    }
  }
  dp
}

/// Factorize remaining_t (which always divides the original t) into 2^a*3^b*5^c*7^d
/// and return the minimum digits needed using the precomputed dp23 table.
#[inline]
fn min_needed(mut rt: i64, dp23: &[Vec<usize>]) -> usize {
  if rt == 1 { return 0; }
  let mut a = 0usize; while rt % 2 == 0 { rt /= 2; a += 1; }
  let mut b = 0usize; while rt % 3 == 0 { rt /= 3; b += 1; }
  let mut c = 0usize; while rt % 5 == 0 { rt /= 5; c += 1; }
  let mut d = 0usize; while rt % 7 == 0 { rt /= 7; d += 1; }
  dp23[a][b] + c + d
}

impl Solution {
  pub fn smallest_number(num: String, t: i64) -> String {
    // Only prime factors 2,3,5,7 can appear as single digits; reject others.
    let mut rem = t;
    for p in [2i64, 3, 5, 7] { while rem % p == 0 { rem /= p; } }
    if rem != 1 { return "-1".to_string(); }

    // Factorize t once to determine dp23 table dimensions.
    let mut tmp = t;
    let mut a_max = 0usize; while tmp % 2 == 0 { tmp /= 2; a_max += 1; }
    let mut b_max = 0usize; while tmp % 3 == 0 { tmp /= 3; b_max += 1; }
    // Build O(a_max * b_max) DP table (no heap allocation for BFS/VecDeque).
    let dp23 = build_dp23(a_max, b_max);

    let digits_ref: Vec<u8> = num.bytes().map(|b| b - b'0').collect();
    let n = digits_ref.len();
    let min_initial = min_needed(t, &dp23);

    let mut buf = Vec::with_capacity(n + 16);

    // Attempt tight fill only when t can be satisfied within n digits.
    if min_initial <= n && Self::fill(&digits_ref, 0, t, true, &mut buf, &dp23) {
      return buf.iter().map(|&d| (d + b'0') as char).collect();
    }

    // Try the smallest number of extra digits that makes t satisfiable.
    // t ≤ 10^14 → at most 15 extra digits suffice.
    let start_extra = min_initial.saturating_sub(n).max(1);
    for extra in start_extra..=15usize {
      buf.clear();
      if Self::fill_free(n + extra, t, &mut buf, &dp23) {
        return buf.iter().map(|&d| (d + b'0') as char).collect();
      }
    }
    "-1".to_string()
  }

  /// Tight fill: greedy with backtracking, constraining result >= num.
  /// Uses exact `min_needed` pruning to avoid dead-end paths.
  fn fill(
    digits: &[u8], pos: usize, remaining_t: i64, tight: bool,
    buf: &mut Vec<u8>, dp23: &[Vec<usize>],
  ) -> bool {
    if pos == digits.len() { return remaining_t == 1; }

    // Product requirement already met: fill the rest greedily.
    if remaining_t == 1 {
      let mut cur_tight = tight;
      for i in pos..digits.len() {
        let lo = if cur_tight { digits[i].max(1) } else { 1u8 };
        buf.push(lo);
        if cur_tight && lo != digits[i] { cur_tight = false; }
      }
      return true;
    }

    let lo = if tight { digits[pos].max(1) } else { 1u8 };
    let slots_after = digits.len() - pos - 1; // positions remaining after this one

    for d in lo..=9u8 {
      let new_rem = remaining_t / gcd64(remaining_t, d as i64);
      // Exact feasibility check: min digits to cover new_rem must fit in slots_after.
      if min_needed(new_rem, dp23) > slots_after { continue; }
      buf.push(d);
      if Self::fill(digits, pos + 1, new_rem, tight && d == digits[pos], buf, dp23) {
        return true;
      }
      buf.pop();
    }
    false
  }

  /// Non-tight fill: pick the smallest `total`-digit zero-free number whose
  /// digit product is divisible by t.  Iterative and backtrack-free:
  /// the exact `min_needed` check ensures every chosen digit leads to a
  /// valid completion, so we never need to undo a choice.
  fn fill_free(total: usize, remaining_t: i64, buf: &mut Vec<u8>, dp23: &[Vec<usize>]) -> bool {
    let mut rem = remaining_t;
    for pos in 0..total {
      if rem == 1 {
        for _ in pos..total { buf.push(1); }
        return true;
      }
      let slots_after = total - pos - 1;
      let mut placed = false;
      for d in 1u8..=9 {
        let new_rem = rem / gcd64(rem, d as i64);
        if min_needed(new_rem, dp23) <= slots_after {
          buf.push(d);
          rem = new_rem;
          placed = true;
          break;
        }
      }
      if !placed { return false; }
    }
    rem == 1
  }
}