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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Ugly Number III

Difficulty: Medium

Problem Description

An ugly number is a positive integer that is divisible by a, b, or c. Given four integers n, a, b, and c, return the n-th ugly number.

Key Insights

  • Ugly numbers are those that can be generated by multiplying a positive integer with the factors a, b, or c.
  • The problem can be solved using a binary search approach to efficiently find the n-th ugly number within a specified range.
  • The count of ugly numbers less than or equal to a number x can be determined using the inclusion-exclusion principle.

Space and Time Complexity

Time Complexity: O(log(2 * 10^9)) due to binary search over the range of ugly numbers. Space Complexity: O(1) as we are using constant space for variables.

Solution

To solve the problem, we can use a binary search algorithm to find the n-th ugly number. We define a function to count how many ugly numbers are less than or equal to a given number x. This count is determined using the principle of inclusion-exclusion for the divisors a, b, and c. The binary search will help us efficiently narrow down to the n-th ugly number by checking the mid-point and adjusting the search range based on the count of ugly numbers.

Code Solutions

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def lcm(x, y):
    return x * (y // gcd(x, y))

def count_ugly_numbers(x, a, b, c):
    ab = lcm(a, b)
    ac = lcm(a, c)
    bc = lcm(b, c)
    abc = lcm(ab, c)
    
    return (x // a) + (x // b) + (x // c) - (x // ab) - (x // ac) - (x // bc) + (x // abc)

def nth_ugly_number(n, a, b, c):
    left, right = 1, 2 * 10**9
    while left < right:
        mid = (left + right) // 2
        if count_ugly_numbers(mid, a, b, c) < n:
            left = mid + 1
        else:
            right = mid
    return left
← Back to All Questions