1201. Ugly Number III

Problem Description

In this problem, you are asked to find the nth 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 nth 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 nth 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 nth ugly number. However, that would be very inefficient for large n.

Instead, we can binary search for the answer because the nth 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 nth ugly number.

Concretely, we calculate mid in our search range as the potential nth 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, and c separately.
• We subtract the numbers that are divisible by the least common multiple (lcm) of (a and b), (b and c), and (a and c) because these numbers were counted more than once.
• We add the numbers divisible by the lcm of (a, b, and c) 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 nth 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 nth ugly number.

Learn more about Math and Binary Search patterns.

Solution Approach

The solution uses a binary search algorithm to find the nth 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:

1. Calculate the least common multiple (LCM) for all pairs and all three numbers: a, b, and c. The LCMs are necessary for the inclusion-exclusion principle to avoid counting duplicates.

   1ab = lcm(a, b)
   2bc = lcm(b, c)
   3ac = lcm(a, c)
   4abc = lcm(a, bc)  # lcm for all three numbers

2. Initialize the binary search boundaries l and r. 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 the nth ugly number lies within this range.

   1l, r = 1, 2 * 10**9

3. The main binary search loop continues until l < r, meaning we haven't yet narrowed down to a single potential option for the nth ugly number.

4. Calculate the middle point (mid) between l and r, which we will test to see if it has exactly n ugly numbers less than or equal to it.

   1mid = (l + r) >> 1  # equivalent to (l + r) // 2 but often faster

5. Apply the inclusion-exclusion principle to count ugly numbers less than or equal to mid:

   1count = (
   2    mid // a +
   3    mid // b +
   4    mid // c -
   5    mid // ab -
   6    mid // bc -
   7    mid // ac +
   8    mid // abc
   9)

6. Compare count with n:

   • If count is greater than or equal to n, it means there are at least n ugly numbers less than or equal to mid, and we need to continue searching in the left half including mid:

     1r = mid

   • If count is less than n, it means there are fewer than n ugly numbers up to mid, and we need to consider larger numbers by searching in the right half:

     1l = mid + 1

7. The loop continues, narrowing the range until l equals r. At this point, l (or r) is the nth ugly number, which we return:

   1return 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.

Example 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.

1. Compute the least common multiples (LCM) for the pairs and all three numbers:

   1ab = lcm(a, b)  # lcm(2, 3) = 6
   2bc = lcm(b, c)  # lcm(3, 5) = 15
   3ac = lcm(a, c)  # lcm(2, 5) = 10
   4abc = lcm(a, bc)  # lcm(2, 15) = 30

2. Initialize binary search bounds:

   1l, r = 1, 2 * 10**9

3. Enter binary search loop:

4. Calculate the midpoint to test:

   1mid = (l + r) >> 1  # Let's assume the midpoint turns out to be 10 for our first iteration

5. Apply inclusion-exclusion to count the ugly numbers less than or equal to mid:

   1count = (
   2    10 // 2 +  # Numbers divisible by 2
   3    10 // 3 +  # Numbers divisible by 3
   4    10 // 5 -  # Numbers divisible by 5
   5    10 // 6 -  # Numbers divisible by both 2 and 3
   6    10 // 15 -  # Numbers divisible by both 3 and 5
   7    10 // 10 +  # Numbers divisible by both 2 and 5
   8    10 // 30   # Numbers divisible by 2, 3, and 5
   9)
   10# This gives us 5 + 3 + 2 - 1 - 0 - 1 + 0 = 8.

6. Since count (8) is less than n (5), we need to consider larger numbers and move l right:

   1l = mid + 1  # Our new `l` is now 11

7. Continue the binary search:

   After several iterations, we will find that when mid = 10, the count is equal to 8, and our l was updated to 11. This process continues until l equals r.

   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 by a, b, or c. 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

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.