We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Ugly Number III

Number: 1307

Difficulty: Medium

Paid? No

Companies: American Express

Problem Description

Given four integers n, a, b, and c, an ugly number is defined as a positive integer that is divisible by at least one of a, b, or c. The task is to find the nth ugly number.

Key Insights

  • Use binary search on the answer space (from 1 to an upper bound like n * min(a, b, c)) to efficiently locate the nth ugly number.
  • Compute the count of ugly numbers ≤ x using the inclusion-exclusion principle.
  • Leverage the formula: count(x) = ⌊x/a⌋ + ⌊x/b⌋ + ⌊x/c⌋ - ⌊x/lcm(a, b)⌋ - ⌊x/lcm(b, c)⌋ - ⌊x/lcm(a, c)⌋ + ⌊x/lcm(a, b, c)⌋.
  • Calculate least common multiples (lcm) using the greatest common divisor (gcd).

Space and Time Complexity

Time Complexity: O(log(max_value)) where max_value is around n * min(a, b, c). Each binary search step does constant time operations. Space Complexity: O(1)

Solution

We perform binary search on the range of potential ugly numbers. For any guess x, the count of numbers ≤ x that are divisible by a, b, or c is obtained via the inclusion-exclusion principle. The gcd and lcm functions are used to count the numbers divisible by the pairs and triplet of divisors. Adjust the binary search window based on whether the count is less than or at least n until the exact nth ugly number is found.

Code Solutions

# Python implementation

import math

def nthUglyNumber(n: int, a: int, b: int, c: int) -> int:
    # Function to compute lcm of two numbers using gcd
    def lcm(x, y):
        return x * y // math.gcd(x, y)
    
    # Compute lcm for pairs and for three numbers
    lcm_ab = lcm(a, b)
    lcm_ac = lcm(a, c)
    lcm_bc = lcm(b, c)
    lcm_abc = lcm(a, lcm(b, c))
    
    # Count ugly numbers <= x using inclusion-exclusion principle
    def count(x):
        return (x // a + x // b + x // c
                - x // lcm_ab - x // lcm_ac - x // lcm_bc
                + x // lcm_abc)
    
    # Set binary search boundaries
    low, high = 1, n * min(a, b, c)
    while low < high:
        mid = (low + high) // 2
        if count(mid) < n:  # Need more numbers, so search in the higher half
            low = mid + 1
        else:
            high = mid  # Found enough numbers, try to reduce x
    return low

# Example usage:
print(nthUglyNumber(3, 2, 3, 5))  # Expected output: 4
← Back to All Questions