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.
Example 1:
Input: n = 10 Output: 12 Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.
Example 2:
Input: n = 1 Output: 1 Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
Constraints:
1 <= n <= 1690The idea is to use an array to store the ugly numbers and use three pointers for 2, 3, and 5 to calculate the next potential ugly numbers. We then choose the minimum of these numbers to be the next ugly number and appropriately move the pointers.
The code defines a function nthUglyNumber that employs dynamic programming with three pointers to generate ugly numbers in sequence and return the nth ugly number. We use an auxiliary array ugly to store ugly numbers, and we maintain pointers i2, i3, and i5 to track the current position of multiplication for 2, 3, and 5 respectively. The next_2, next_3, and next_5 variables hold the next potential candidates for ugly numbers, and we compute the next ugly number as the minimum of these three values.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of ugly numbers to generate.
Space Complexity: O(n), for storing the ugly numbers array.
This method involves using a min-heap to manage the sequence of potential ugly numbers. We start with 1 in the min-heap and repeatedly extract the smallest element, multiplying it by 2, 3, and 5 to generate new candidates, which are then inserted back into the heap. Duplicate entries are avoided by using a set for tracking which numbers have been added to the heap.
The solution uses a min-heap to keep track of and retrieve the smallest ugly number, avoiding duplicates by using a set. It generates ugly numbers by multiplying the current smallest number by 2, 3, and 5, inserting valid new numbers back into the heap.
Python
Time Complexity: O(n log n), primarily due to heap operations.
Space Complexity: O(n), for data structures that might store up to n numbers.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Three Pointers | Time Complexity: |
| Min-Heap Approach | Time Complexity: |
Ugly Number - Leetcode 263 - Python • NeetCode • 28,295 views views
Watch 9 more video solutions →Practice Ugly Number II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor