Leetcode Problem 264. Ugly Number II

264. Ugly Number II

Leetcode Solutions

Dynamic Programming Approach to Find the nth Ugly Number

  1. Initialize an array nums with a size of 1690 and set the first element to 1 (the first ugly number).
  2. Initialize three pointers i2, i3, and i5 to 0, which will track the position of the last number multiplied by 2, 3, and 5, respectively.
  3. Loop 1689 times (since the first ugly number is already in the array) to fill the rest of the nums array with ugly numbers.
  4. At each iteration, calculate the next ugly number by selecting the minimum of nums[i2] * 2, nums[i3] * 3, and nums[i5] * 5.
  5. Add the selected minimum number to the nums array.
  6. Increment the pointer (i2, i3, or i5) that corresponds to the minimum number chosen.
  7. After the loop, return the nth element of the nums array.
UML Thumbnail

Heap-based Approach to Find the nth Ugly Number

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...