Domain 2MediumMEDIUM

Ugly Number III

Uses binary search on the answer range combined with inclusion-exclusion to count valid numbers efficiently, avoiding brute force iteration.

Domain: medium•Updated: 2026-09-10
#binary search#mathematics#inclusion-exclusion principle

Problem Breakdown

We are asked to find the nn-th positive integer that is divisible by at least one of three given integers a, b, or c. These numbers are colloquially called “ugly” in this specific problem context (distinct from the standard definition involving prime factors 2, 3, and 5).

Inputs:

  • n: The rank we want to find (1≤n≤1091 \le n \le 10^9).
  • a, b, c: Divisors (1≤a,b,c≤1091 \le a,b,c \le 10^9).

Output:

  • An integer representing the nn-th ugly number.

Implicit Constraints & Edge Cases:

  • Monotonicity: The count of valid numbers up to any value x is non-decreasing with respect to x. This property allows for Binary Search.
  • Overlaps (Inclusion-Exclusion): A number might be divisible by both a and b, or all three. We must account for these overlaps using the Principle of Inclusion-Exclusion to avoid double counting in our check function.
    • Count = ⌊x/a⌋+⌊x/b⌋+⌊x/c⌋\lfloor x/a \rfloor + \lfloor x/b \rfloor + \lfloor x/c \rfloor
    • Minus: ⌊x/lcm(a,b)⌋\lfloor x/\text{lcm}(a,b) \rfloor, ⌊x/lcm(b,c)⌋\lfloor x/\text{lcm}(b,c) \rfloor, ⌊x/lcm(c,a)⌋\lfloor x/\text{lcm}(c,a) \rfloor
    • Plus: ⌊x/lcm(a,b,c)⌋\lfloor x/\text{lcm}(a,b,c) \rfloor
  • Range: The problem guarantees the result is within [1, 2 * 10^9]. This gives us a safe upper bound for our binary search.

Intuition

A naive approach would be to iterate through integers starting from 1, checking if each is divisible by a, b, or c, and incrementing a counter until we reach n.

  • Brute Force Complexity: O(Answer)O(\text{Answer}). Since the answer can be up to ≈2⋅109\approx 2 \cdot 10^9, this will result in Time Limit Exceeded (TLE).

Key Insight: Instead of generating numbers, let’s count how many ugly numbers exist within a range [1, x]. Let count(x) denote this number.

  • If we can calculate count(x) efficiently, the function is monotonic: if x increases, count(x) never decreases.
  • We want to find the smallest x such that count(x) >= n. This structure screams Binary Search.

Optimal Approach: Combine Binary Search with Inclusion-Exclusion Principle for counting.

Approach

  1. Define a helper function check(limit, a, b, c) which returns the number of ugly numbers ≤\le limit using inclusion-exclusion:
    • Sum counts of multiples of each individual divisor.
    • Subtract counts of multiples of pairwise LCMs (to remove double counting).
    • Add count of multiples of triple LCM (to add back what was subtracted too many times).
  2. Set up Binary Search for the answer x:
    • Low: The smallest possible ugly number is min⁡(a,b,c)\min(a, b, c). We can start at 1 or that minimum; starting at 1 simplifies logic without cost.
    • High: Based on constraints and mathematical properties (n×min⁡(a,b,c)n \times \min(a,b,c)), a safe upper bound exists within the problem’s guaranteed range limits (approx 2⋅1092 \cdot 10^9). We’ll use n * min(a, b, c) as it is mathematically sufficient.
  3. Binary Search Logic:
    • While low < high:
      • Calculate mid = low + (high - low) // 2.
      • If check(mid, ...) ≥n\ge n, then the target is at most mid, so set high = mid (try smaller).
      • Else (count < n), we need a larger range to find more numbers: low = mid + 1.
    • Return low.

Complexity Analysis

  • Time Complexity: O(log⁡K)O(\log K), where KK is the upper bound of the answer (approx. 2⋅1092 \cdot 10^9). The binary search performs roughly log⁡2(2⋅109)≈31\log_2(2 \cdot 10^9) \approx 31 iterations. Inside each iteration, we perform constant number arithmetic operations and GCD calculations (O(log⁡(val))O(\log(\text{val}))), which is negligible compared to the loop count.
  • Space Complexity: O(1)O(1) - only a few integer variables are used for calculation.

Solution

def nthUglyNumber(n: int, a: int, b: int, c: int) -> int:
    # Helper function to calculate GCD using Euclidean algorithm
    def gcd(x: int, y: int) -> int:
        while y:
            x, y = y, x % y
        return x
    
    # Helper function to calculate LCM safely. 
    # Python handles large integers automatically so overflow isn't an issue here.
    def lcm(x: int, y: int) -> int:
        if x == 0 or y == 0: return 0 
        return (x * y) // gcd(x, y)

    # Function to count ugly numbers <= limit using Inclusion-Exclusion Principle
    def count(limit):
        ab = lcm(a, b)
        ac = lcm(a, c)
        bc = lcm(b, c)
        abc = lcm(ab, c) 
        
        return (limit // a + 
                limit // b + 
                limit // c - 
                limit // ab - 
                limit // ac - 
                limit // bc + 
                limit // abc)

    # Binary Search for the smallest number with count >= n
    low = 1
    high = n * min(a, b, c) 
    
    while low < high:
        mid = (low + high) // 2
        if count(mid) >= n:
            high = mid
        else:
            low = mid + 1
            
    return low

# Example usage / Test cases logic would go here in a real file, 
# but for the interview solution we just define and call.

Edge Cases Handled

  • Duplicate Divisors: If a == b, lcm(a,b) equals a. The inclusion-exclusion formula correctly subtracts multiples of a once (via pairwise) while adding back via triple overlap, ensuring no double counting errors occur despite identical inputs.
  • Large Inputs (10910^9): Python handles large integers automatically without overflow issues common in C++/Java fixed-width types. The binary search range is adjusted to fit the problem guarantees.
  • Result Range: We rely on the constraint guarantee that result ≤2⋅109\le 2 \cdot 10^9. If this weren’t guaranteed, we would need a dynamic upper bound calculation (e.g., n * min(a,b,c)), which is implemented here as it covers all valid cases safely.
  • LCM Calculation: We ensure LCM is computed correctly even if inputs are not coprime by dividing the product of two numbers by their GCD before multiplying with the third, preventing unnecessary intermediate explosion in languages like C++ (though Python handles it).