Ugly Number III
MedPrompt
An ugly number is a positive integer that is divisible by a, b, or c.
Given four integers n, a, b, and c, return the nth ugly number.
Example 1:
Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.Example 2:
Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.Example 3:
Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.
Constraints:
1 <= n, a, b, c <= 1091 <= a * b * c <= 1018- It is guaranteed that the result will be in range
[1, 2 * 109].
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves a straightforward simulation. We iterate through positive integers starting from 1, and for each number, we check if it's divisible by a, b, or c. We maintain a counter for the ugly numbers found. When the counter reaches n, the current integer is our answer.
Algorithm
- Initialize a counter
countto 0 and the current numbernumto 0. - Enter a loop that continues until
countequalsn. - Inside the loop, increment
num. - Check if
numis divisible bya,b, orc(i.e.,num % a == 0 || num % b == 0 || num % c == 0). - If it is, increment the
count. - Once the loop terminates (when
count == n),numholds the value of the n-th ugly number.
Walkthrough
The algorithm works by iterating through numbers one by one and checking if they meet the criteria of an ugly number. It's the most intuitive way to think about the problem but fails to scale.
class Solution { public int nthUglyNumber(int n, int a, int b, int c) { int count = 0; int num = 0; while (count < n) { num++; if (num % a == 0 || num % b == 0 || num % c == 0) { count++; } } return num; }}This method is easy to understand but is too slow for the given constraints, as the n-th ugly number can be as large as 2 * 10^9, leading to a very high number of iterations.
Complexity
Time
O(K), where K is the value of the n-th ugly number. In the worst case, K can be up to 2 * 10^9, making this approach infeasible.
Space
O(1) as we only use a few variables to store the count and the current number.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
Solutions
Solution
class Solution { public int nthUglyNumber ( int n , int a , int b , int c ) { long ab = lcm ( a , b ); long bc = lcm ( b , c ); long ac = lcm ( a , c ); long abc = lcm ( ab , c ); long l = 1 , r = 2000000000 ; while ( l < r ) { long mid = ( l + r ) >> 1 ; if ( mid / a + mid / b + mid / c - mid / ab - mid / bc - mid / ac + mid / abc >= n ) { r = mid ; } else { l = mid + 1 ; } } return ( int ) l ; } private long gcd ( long a , long b ) { return b == 0 ? a : gcd ( b , a % b ); } private long lcm ( long a , long b ) { return a * b / gcd ( a , b ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.