Solution Explanation: Finding the nth Ugly Number

This problem asks us to find the nth ugly number, where an ugly number is a positive integer divisible by at least one of three given integers (a, b, c). A direct approach of generating ugly numbers until we reach the nth one would be inefficient for large n. Instead, we employ a binary search strategy combined with the inclusion-exclusion principle.

1. Inclusion-Exclusion Principle:

The core idea is to efficiently count the number of ugly numbers less than or equal to a given number x. We can't simply sum the counts of numbers divisible by a, b, and c individually, because some numbers might be divisible by multiple of these numbers. The inclusion-exclusion principle helps us correct for this overcounting:

• Count numbers divisible by a, b, or c individually: ⌊x/a⌋ + ⌊x/b⌋ + ⌊x/c⌋
• Subtract numbers divisible by at least two of a, b, c: ⌊x/lcm(a,b)⌋ + ⌊x/lcm(a,c)⌋ + ⌊x/lcm(b,c)⌋ (lcm = least common multiple)
• Add back numbers divisible by all three (a, b, c): ⌊x/lcm(a,b,c)⌋

The formula becomes:

count(x) = ⌊x/a⌋ + ⌊x/b⌋ + ⌊x/c⌋ - ⌊x/lcm(a,b)⌋ - ⌊x/lcm(a,c)⌋ - ⌊x/lcm(b,c)⌋ + ⌊x/lcm(a,b,c)⌋

2. Binary Search:

Now that we have a way to count ugly numbers up to a given x, we can use binary search to find the smallest x such that count(x) >= n.

• We initialize the search space: left = 1, right = 2 * 10^9 (as per problem constraints).
• In each iteration:
  • Calculate mid = (left + right) / 2.
  • Evaluate count(mid) using the inclusion-exclusion formula.
  • If count(mid) >= n, the nth ugly number is in the range [left, mid], so we update right = mid.
  • Otherwise, the nth ugly number is in the range [mid + 1, right], so we update left = mid + 1.
• The loop continues until left == right, at which point left (or right) is the nth ugly number.

3. Time and Space Complexity:

• Time Complexity: The binary search takes O(log m) time, where m is the upper bound (2 * 10^9). The calculation of count(x) within each iteration is O(1), as it involves a fixed number of arithmetic operations. Therefore, the overall time complexity is O(log m).

• Space Complexity: The algorithm uses a constant amount of extra space for variables, so the space complexity is O(1).

Code Implementation (Python):

import math
 
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
 
def lcm(a, b):
    return (a * b) // gcd(a, b)
 
class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        ab = lcm(a, b)
        bc = lcm(b, c)
        ac = lcm(a, c)
        abc = lcm(a, bc)  # lcm(a, b, c)
 
        left, right = 1, 2 * 10**9
        while left < right:
            mid = (left + right) // 2
            count = mid // a + mid // b + mid // c - mid // ab - mid // bc - mid // ac + mid // abc
            if count >= n:
                right = mid
            else:
                left = mid + 1
        return left

The code in other languages (Java, C++, Go, TypeScript) follows the same algorithmic logic, with adjustments for language-specific syntax and data types (e.g., using long or bigint for larger numbers in Java, C++, Go and TypeScript). The gcd and lcm helper functions are implemented similarly across all languages.