Ugly number ii

Hash Table Math Dynamic Programming Heap (Priority Queue)

49.5% acceptance

Jan 12, 2026

6848

445

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return the nth ugly number.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn nth_ugly_number(n: i32) -> i32 {
    let n = n as usize;
    let mut ugly = vec![1; n];
    let mut i2 = 0;
    let mut i3 = 0;
    let mut i5 = 0;
    
    for i in 1..n {
      let next2 = ugly[i2] * 2;
      let next3 = ugly[i3] * 3;
      let next5 = ugly[i5] * 5;
      
      ugly[i] = next2.min(next3).min(next5);
      
      if ugly[i] == next2 {
        i2 += 1;
      }
      if ugly[i] == next3 {
        i3 += 1;
      }
      if ugly[i] == next5 {
        i5 += 1;
      }
    }
    
    ugly[n - 1]
  }
}