1201. Ugly Number III
Problem Description
In this problem, you are asked to find the n
th ugly number. An ugly number is defined as a positive integer that is divisible by any of the given three integers a
, b
, or c
. The integers a
, b
, and c
are the only prime factors considered for ugliness. You need to return the smallest n
th number that meets the condition of being an ugly number.
Intuition
The intuition behind the solution is to use binary search to efficiently find the n
th ugly number. A straightforward way to solve it would be to iterate over numbers starting from 1, and count how many of them are divisible by a
, b
, or c
until we reach the n
th ugly number. However, that would be very inefficient for large n
.
Instead, we can binary search for the answer because the n
th ugly number is within a known range. The smallest ugly number is 1, and by setting an upper bound (like 2 * 10^9), we can use binary search to narrow down the number that is exactly the n
th ugly number.
Concretely, we calculate mid
in our search range as the potential n
th ugly number, and check how many numbers less than or equal to mid
are divisible by a
, b
, or c
. To avoid counting numbers more than once that are divisible by any two or all three of a
, b
, and c
, we use the inclusion-exclusion principle. This involves adding and subtracting counts of multiples, like adding the count of numbers divisible by a
and by b
but then subtracting the count of numbers divisible by both a
and b
to remove the duplicates.
Here's how we apply inclusion-exclusion in this context:
- We count numbers divisible by
a
,b
, andc
separately. - We subtract the numbers that are divisible by the least common multiple (lcm) of (
a
andb
), (b
andc
), and (a
andc
) because these numbers were counted more than once. - We add the numbers divisible by the lcm of (
a
,b
, andc
) since those numbers were subtracted one time too many.
Once we have the count of ugly numbers less than or equal to mid
, we compare it with n
. If our count is equal to or greater than n
, the n
th ugly number is less than or equal to mid
, and we continue searching to the left. Otherwise, we continue searching to the right.
The process repeats, narrowing the search range until the left and right boundaries converge, at which point l
or r
will be the n
th ugly number.
Learn more about Math and Binary Search patterns.
Solution Approach
The solution uses a binary search algorithm to find the n
th ugly number. Binary search is a widely used algorithm for finding an item from a sorted list or in scenarios like this one where the condition is monotonically increasing or decreasing.
Here is a step-by-step explanation of the implementation:
-
Calculate the least common multiple (LCM) for all pairs and all three numbers:
a
,b
, andc
. The LCMs are necessary for the inclusion-exclusion principle to avoid counting duplicates.ab = lcm(a, b) bc = lcm(b, c) ac = lcm(a, c) abc = lcm(a, bc) # lcm for all three numbers
-
Initialize the binary search boundaries
l
andr
. The left boundary (l
) starts at 1, as the smallest ugly number is 1. The right boundary (r
) is set to a high value, ensuring that then
th ugly number lies within this range.l, r = 1, 2 * 10**9
-
The main binary search loop continues until
l < r
, meaning we haven't yet narrowed down to a single potential option for then
th ugly number. -
Calculate the middle point (
mid
) betweenl
andr
, which we will test to see if it has exactlyn
ugly numbers less than or equal to it.mid = (l + r) >> 1 # equivalent to (l + r) // 2 but often faster
-
Apply the inclusion-exclusion principle to count ugly numbers less than or equal to
mid
:count = ( mid // a + mid // b + mid // c - mid // ab - mid // bc - mid // ac + mid // abc )
-
Compare
count
withn
:-
If
count
is greater than or equal ton
, it means there are at leastn
ugly numbers less than or equal tomid
, and we need to continue searching in the left half includingmid
:r = mid
-
If
count
is less thann
, it means there are fewer thann
ugly numbers up tomid
, and we need to consider larger numbers by searching in the right half:l = mid + 1
-
-
The loop continues, narrowing the range until
l
equalsr
. At this point,l
(orr
) is then
th ugly number, which we return:return l
This approach is efficient because it reduces the problem space exponentially with each iteration of the binary search rather than iterating sequentially through all numbers, which wouldn't be feasible for large values of n
.
Note: This solution assumes the existence of a function lcm
which computes the least common multiple of the given numbers. Implementing or using a library function for LCM calculations is beyond the scope of the explanation but is critical for the solution to work correctly.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example by applying the solution approach outlined above. Suppose we have a = 2
, b = 3
, and c = 5
, and we want to find the 5th ugly number.
-
Compute the least common multiples (LCM) for the pairs and all three numbers:
ab = lcm(a, b) # lcm(2, 3) = 6 bc = lcm(b, c) # lcm(3, 5) = 15 ac = lcm(a, c) # lcm(2, 5) = 10 abc = lcm(a, bc) # lcm(2, 15) = 30
-
Initialize binary search bounds:
l, r = 1, 2 * 10**9
-
Enter binary search loop:
-
Calculate the midpoint to test:
mid = (l + r) >> 1 # Let's assume the midpoint turns out to be 10 for our first iteration
-
Apply inclusion-exclusion to count the ugly numbers less than or equal to
mid
:count = ( 10 // 2 + # Numbers divisible by 2 10 // 3 + # Numbers divisible by 3 10 // 5 - # Numbers divisible by 5 10 // 6 - # Numbers divisible by both 2 and 3 10 // 15 - # Numbers divisible by both 3 and 5 10 // 10 + # Numbers divisible by both 2 and 5 10 // 30 # Numbers divisible by 2, 3, and 5 ) # This gives us 5 + 3 + 2 - 1 - 0 - 1 + 0 = 8.
-
Since
count
(8) is less thann
(5), we need to consider larger numbers and movel
right:l = mid + 1 # Our new `l` is now 11
-
Continue the binary search:
After several iterations, we will find that when
mid = 10
, the count is equal to 8, and ourl
was updated to 11. This process continues untill
equalsr
.Ultimately, we will find that
l = r = 10
because that is the smallest number for which there are exactly 5 or more numbers that are divisible bya
,b
, orc
. So the 5th ugly number is 10.
This example illustrates how the solution uses binary search and the inclusion-exclusion principle to efficiently find the target ugly number without iterating over every single number up to n
.
Solution Implementation
1from math import gcd
2
3# The lcm function computes the least common multiple of two or more numbers
4def lcm(x, y, z=None):
5 def lcm_two(a, b):
6 return a * b // gcd(a, b)
7
8 if z: # if three numbers are provided
9 return lcm_two(lcm_two(x, y), z)
10 else: # if only two numbers are provided
11 return lcm_two(x, y)
12
13class Solution:
14 def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
15 # Computing least common multiples of pairs and triplet of a, b, c
16 ab_lcm = lcm(a, b)
17 bc_lcm = lcm(b, c)
18 ac_lcm = lcm(a, c)
19 abc_lcm = lcm(a, b, c)
20
21 # Binary search range - start with 1, end with a value large enough to ensure the nth ugly number is within the range
22 left, right = 1, 2 * 10**9
23
24 # Binary search to find the nth ugly number
25 while left < right:
26 mid = (left + right) // 2
27
28 # Counting the number of ugly numbers up to `mid`
29 # by adding the count for each prime and subtracting the count for
30 # their least common multiples to avoid double counting.
31 count = (mid // a + mid // b + mid // c
32 - mid // ab_lcm
33 - mid // bc_lcm
34 - mid // ac_lcm
35 + mid // abc_lcm)
36
37 # If the current count is at least `n`, move `right` to mid
38 # indicating that the nth ugly number is lesser or equal to mid.
39 if count >= n:
40 right = mid
41 else:
42 # Otherwise, move `left` just above mid as the nth ugly
43 # number must be greater than mid.
44 left = mid + 1
45
46 # Since 'left' will end up at the smallest number
47 # where the count is at least n, it is our answer.
48 return left
49
1class Solution {
2 // Method to find the nth ugly number that is divisible by a, b, or c
3 public int nthUglyNumber(int n, int a, int b, int c) {
4 // Find the least common multiple (LCM) of the pairs (a, b), (b, c), (a, c),
5 // and the three numbers (a, b, c)
6 long lcmAB = lcm(a, b);
7 long lcmBC = lcm(b, c);
8 long lcmAC = lcm(a, c);
9 long lcmABC = lcm(lcmAB, c);
10
11 // Use binary search in the range [1, 2000000000] to find the nth ugly number
12 long left = 1, right = 2000000000;
13 while (left < right) {
14 long mid = (left + right) >> 1; // Calculate the midpoint of the range
15 // Check if the count of numbers divisible by a, b, or c up to mid is >= n
16 if (count(mid, a, b, c, lcmAB, lcmBC, lcmAC, lcmABC) >= n) {
17 right = mid;
18 } else {
19 left = mid + 1;
20 }
21 }
22 // The left pointer will point to the nth ugly number
23 return (int) left;
24 }
25
26 // Helper method to count numbers divisible by a, b, or c up to a limit
27 private long count(long mid, int a, int b, int c, long lcmAB, long lcmBC, long lcmAC, long lcmABC) {
28 // Calculate the inclusive count of divisible numbers by a, b, and c separately
29 long countA = mid / a;
30 long countB = mid / b;
31 long countC = mid / c;
32
33 // Subtract the counts for pairs of (a, b), (b, c), (a, c) to exclude double counted numbers
34 long countAB = mid / lcmAB;
35 long countBC = mid / lcmBC;
36 long countAC = mid / lcmAC;
37
38 // Add the count for (a, b, c) to include numbers that are divisible by all three
39 long countABC = mid / lcmABC;
40
41 // Apply inclusion-exclusion principle and return the result
42 return countA + countB + countC - countAB - countBC - countAC + countABC;
43 }
44
45 // Helper method to find the greatest common divisor (GCD) of two numbers
46 private long gcd(long a, long b) {
47 return b == 0 ? a : gcd(b, a % b);
48 }
49
50 // Helper method to find the least common multiple (LCM) of two numbers
51 private long lcm(long a, long b) {
52 return a * b / gcd(a, b);
53 }
54}
55
1class Solution {
2public:
3 // Utility function to calculate the least common multiple (LCM) of two numbers
4 long long lcm(long long a, long long b) {
5 return a / gcd(a, b) * b; // Calculate the product and then divide by the greatest common divisor (GCD)
6 }
7
8 // Utility function to calculate the greatest common divisor (GCD) of two numbers
9 long long gcd(long long a, long long b) {
10 if (b == 0) return a; // Base case: if the second number is 0, return the first number
11 return gcd(b, a % b); // Recursive case: return the GCD of b and the remainder of a divided by b
12 }
13
14 // Function to find the nth ugly number that is divisible by at least one of the given numbers a, b, or c
15 int nthUglyNumber(int n, int a, int b, int c) {
16 // Compute pairwise least common multiples
17 long long lcmAB = lcm(a, b);
18 long long lcmBC = lcm(b, c);
19 long long lcmAC = lcm(a, c);
20 // Compute the least common multiple of all three numbers
21 long long lcmABC = lcm(lcmAB, c);
22
23 long long left = 1, right = 2000000000;
24 // Binary search to find the smallest integer that has at least n multiples of a, b, or c
25 while (left < right) {
26 long long mid = (left + right) / 2;
27 // Count the number of multiples of a, b, c, and subtract the multiples of lcmAB, lcmBC, lcmAC
28 // Add the multiples of lcmABC to correct for over-subtraction
29 long long count = mid / a + mid / b + mid / c
30 - mid / lcmAB - mid / lcmBC - mid / lcmAC
31 + mid / lcmABC;
32 if (count >= n) { // If there are at least n ugly numbers up to mid, search the left half
33 right = mid;
34 } else { // Otherwise, search the right half
35 left = mid + 1;
36 }
37 }
38 // The left index now points to the nth ugly number
39 return left;
40 }
41};
42
1// Function to calculate the gcd of two numbers using the Euclidean algorithm.
2function gcd(a: bigint, b: bigint): bigint {
3 while (b !== 0n) {
4 let temp = b;
5 b = a % b;
6 a = temp;
7 }
8 return a;
9}
10
11// Function to calculate the lcm of two numbers based on the gcd.
12function lcm(a: bigint, b: bigint): bigint {
13 return (a / gcd(a, b)) * b;
14}
15
16// Function to find the nth ugly number that is divisible by either a, b, or c.
17function nthUglyNumber(n: number, a: number, b: number, c: number): number {
18 // Convert inputs to bigint for proper lcm and gcd calculations.
19 const bigA = BigInt(a);
20 const bigB = BigInt(b);
21 const bigC = BigInt(c);
22
23 // Calculate least common multiples for combinations of a, b, and c.
24 const abLCM = lcm(bigA, bigB);
25 const bcLCM = lcm(bigB, bigC);
26 const acLCM = lcm(bigA, bigC);
27 const abcLCM = lcm(bigA, bcLCM);
28
29 // Binary search to find the nth ugly number.
30 let low = 1n;
31 let high = BigInt(2e9);
32 while (low < high) {
33 const mid = (low + high) >> 1n;
34 // Calculate the count of numbers divisible by a, b, or c up to `mid`.
35 const count =
36 mid / bigA +
37 mid / bigB +
38 mid / bigC -
39 mid / abLCM -
40 mid / bcLCM -
41 mid / acLCM +
42 mid / abcLCM;
43 // Narrow down search space based on `count` compared to `n`.
44 if (count >= BigInt(n)) {
45 high = mid;
46 } else {
47 low = mid + 1n;
48 }
49 }
50
51 // Return the nth ugly number as a Number type.
52 return Number(low);
53}
54
Time and Space Complexity
Time Complexity
The time complexity of the given code primarily depends upon the binary search used to find the nth
ugly number. The binary search operates in the range between 1
and 2 * 10**9
. In each iteration of the binary search, we perform a constant number of operations including the computation of lcm
(Least Common Multiple), divisions, and some arithmetic operations.
The binary search halves the search range with each iteration, which results in a time complexity of O(log(maxVal))
, where maxVal
is 2 * 10**9
.
Additionally, the calculations of lcm(a, b)
, lcm(b, c)
, lcm(a, c)
, and lcm(a, b, c)
are executed only once and outside of the loop, assuming that the lcm
function has a time complexity of O(log(min(x, y)))
for two numbers x
and y
, where lcm(a, b, c)
uses the pairwise method to calculate LCM of three numbers which can be expressed as lcm(a, lcm(b, c))
.
Thus, the overall time complexity is O(4 * log(min(a, b, c)) + log(maxVal))
. Because log(min(a, b, c))
is negligible compared to log(maxVal)
, the practical time complexity simplifies to O(log(maxVal))
, which can be stated as O(log(2 * 10**9))
for this specific problem.
Space Complexity
The space complexity of the algorithm is O(1)
. No additional space that scales with the input size is used. The space is used for a constant number of integer variables (ab
, bc
, ac
, abc
, l
, r
, mid
, and the LCM calculations), regardless of the size of the input n
, a
, b
, or c
. Thus, the space complexity remains constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!