Super ugly number

Array Math Dynamic Programming

46.0% acceptance

Jan 12, 2026

2284

408

A super ugly number is a positive integer whose prime factors are in the array primes. Given an integer n and an array of integers primes, return the nth super ugly number. The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn nth_super_ugly_number(n: i32, primes: Vec<i32>) -> i32 {
    let n = n as usize;
    let k = primes.len();
    let mut dp = vec![1i64; n];
    let mut pointers = vec![0; k];
    let primes: Vec<i64> = primes.iter().map(|&x| x as i64).collect();
    
    for i in 1..n {
      let mut min_val = i64::MAX;
      for j in 0..k {
        min_val = min_val.min(dp[pointers[j]] * primes[j]);
      }
      dp[i] = min_val;
      
      for j in 0..k {
        if dp[pointers[j]] * primes[j] == min_val {
          pointers[j] += 1;
        }
      }
    }
    
    dp[n - 1] as i32
  }
}