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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

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

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.


Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄