Problem Description

An ugly number in this problem is defined as a positive integer that is divisible by at least one of the given values a, b, or c.

Given four integers:

• n: the position of the ugly number we want to find
• a, b, c: the divisors that define ugly numbers

The task is to find the n-th ugly number in the sequence when ugly numbers are arranged in ascending order.

For example, if a = 2, b = 3, and c = 5, then the ugly numbers would be those divisible by 2, 3, or 5. The sequence would start as: 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20...

The challenge is to efficiently find the n-th number in this sequence without generating all ugly numbers up to that position, which would be inefficient for large values of n.

The solution uses binary search combined with the inclusion-exclusion principle to count how many ugly numbers exist up to a given value x. By finding the smallest x such that exactly n ugly numbers are less than or equal to x, we can determine the n-th ugly number.

The counting formula uses:

• Add numbers divisible by a, b, or c individually
• Subtract numbers divisible by pairs (to avoid double counting)
• Add back numbers divisible by all three (to correct for triple subtraction)

This approach allows finding the answer in O(log(2×10^9)) time complexity.

Intuition

The key insight is to reframe the problem: instead of directly finding the n-th ugly number, we ask "what is the smallest number x such that there are exactly n ugly numbers less than or equal to x?"

This reframing is powerful because:

1. If we can count how many ugly numbers exist up to any value x, we can use binary search to find our answer
2. Counting ugly numbers up to x is much easier than generating them in sequence

To count ugly numbers up to x, we need to count how many numbers from 1 to x are divisible by a, b, or c. Initially, we might think to just add x//a + x//b + x//c, but this has a problem - we're counting some numbers multiple times!

For instance, if a=2 and b=3, the number 6 is divisible by both, so it gets counted twice. This leads us to the inclusion-exclusion principle:

• First, include all numbers divisible by a, b, or c
• Then exclude (subtract) numbers we counted twice - those divisible by both a and b, both a and c, or both b and c
• But wait! Numbers divisible by all three (like 30 when a=2, b=3, c=5) were added 3 times initially, then subtracted 3 times, so they're completely missing. We need to add them back once.

This gives us the formula:

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

Now we can use binary search on the range [1, 2×10^9]. For each midpoint, we check if it contains at least n ugly numbers. If yes, the answer might be this value or smaller; if no, we need a larger value. The binary search converges to the exact n-th ugly number.

Learn more about Math, Binary Search and Combinatorics patterns.

Solution Approach

The implementation uses the binary search template combined with the inclusion-exclusion principle to efficiently find the n-th ugly number.

Step 1: Pre-calculate LCMs First, we calculate the least common multiples (LCMs) that we'll need for the inclusion-exclusion formula:

• ab = lcm(a, b) - for numbers divisible by both a and b
• bc = lcm(b, c) - for numbers divisible by both b and c
• ac = lcm(a, c) - for numbers divisible by both a and c
• abc = lcm(a, b, c) - for numbers divisible by all three

Step 2: Define the Feasible Function The feasible function checks if there are at least n ugly numbers less than or equal to x:

def feasible(x):
    count = x//a + x//b + x//c - x//lcm_ab - x//lcm_bc - x//lcm_ac + x//lcm_abc
    return count >= n

This creates a boolean array pattern like: [false, false, ..., true, true, true] where we want to find the first true (the smallest x where count >= n).

Step 3: Binary Search Using the Template We use the standard binary search template:

left, right = 1, 2 * 10**9
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index

Why this works:

• The search space is [1, 2×10^9] where we're looking for the smallest x such that there are at least n ugly numbers ≤ x
• first_true_index tracks the smallest value found so far where feasible(mid) is true
• When feasible(mid) is true, we save mid as a candidate and search left for a potentially smaller answer
• When feasible(mid) is false, we search right for a larger value
• The loop uses while left <= right to ensure we check all candidates

Time Complexity: O(log(2×10^9)) ≈ O(31) = O(1) for the binary search iterations, with O(1) work per iteration.

Space Complexity: O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's find the 4th ugly number where a = 2, b = 3, and c = 5.

Step 1: Pre-calculate LCMs

• lcm(2, 3) = 6
• lcm(2, 5) = 10
• lcm(3, 5) = 15
• lcm(2, 3, 5) = 30

Step 2: Binary Search Setup

• Initial range: [l=1, r=2000000000]

Step 3: Binary Search Iterations

Iteration 1:

• mid = 1000000000
• Count ugly numbers ≤ 1000000000:
  • Divisible by 2: 1000000000/2 = 500000000
  • Divisible by 3: 1000000000/3 = 333333333
  • Divisible by 5: 1000000000/5 = 200000000
  • Divisible by both 2 and 3 (lcm=6): 1000000000/6 = 166666666
  • Divisible by both 2 and 5 (lcm=10): 1000000000/10 = 100000000
  • Divisible by both 3 and 5 (lcm=15): 1000000000/15 = 66666666
  • Divisible by all three (lcm=30): 1000000000/30 = 33333333
  • Total: 500000000 + 333333333 + 200000000 - 166666666 - 100000000 - 66666666 + 33333333 = 733333334
• Since 733333334 >= 4, search left half: r = 1000000000

Iteration 2:

• mid = 500000000
• Count = 366666667 (using same formula)
• Since 366666667 >= 4, search left half: r = 500000000

[Many iterations later, as we narrow down...]

Near-final iterations:

• Range narrows to [l=4, r=8]
• mid = 6
• Count ugly numbers ≤ 6:
  • Divisible by 2: 6/2 = 3 → {2, 4, 6}
  • Divisible by 3: 6/3 = 2 → {3, 6}
  • Divisible by 5: 6/5 = 1 → {5}
  • Divisible by 6: 6/6 = 1 → {6} (already counted in both 2 and 3)
  • Divisible by 10: 6/10 = 0 → none
  • Divisible by 15: 6/15 = 0 → none
  • Divisible by 30: 6/30 = 0 → none
  • Total: 3 + 2 + 1 - 1 - 0 - 0 + 0 = 5
• Since 5 >= 4, search left half: r = 6

Next iteration:

• Range is [l=4, r=6]
• mid = 5
• Count ugly numbers ≤ 5:
  • Divisible by 2: 5/2 = 2 → {2, 4}
  • Divisible by 3: 5/3 = 1 → {3}
  • Divisible by 5: 5/5 = 1 → {5}
  • No overlaps (6 > 5, 10 > 5, 15 > 5, 30 > 5)
  • Total: 2 + 1 + 1 - 0 - 0 - 0 + 0 = 4
• Since 4 >= 4, search left half: r = 5

Final iteration:

• Range is [l=4, r=5]
• mid = 4
• Count ugly numbers ≤ 4:
  • Divisible by 2: 4/2 = 2 → {2, 4}
  • Divisible by 3: 4/3 = 1 → {3}
  • Divisible by 5: 4/5 = 0 → none
  • Total: 2 + 1 + 0 - 0 - 0 - 0 + 0 = 3
• Since 3 < 4, search right half: l = 5

Result: l = r = 5

The 4th ugly number is 5. We can verify: the sequence is {2, 3, 4, 5, ...}, and indeed 5 is the 4th number.

Solution Implementation

Time and Space Complexity

The time complexity is O(log m), where m = 2 × 10^9. This is because the algorithm uses binary search on the range [1, 2 × 10^9]. In each iteration, the search space is halved, requiring at most log₂(2 × 10^9) ≈ 31 iterations. Within each iteration, the operations performed are:

• Computing mid = (l + r) >> 1: O(1)
• Calculating the count using inclusion-exclusion principle with divisions: mid // a + mid // b + mid // c - mid // ab - mid // bc - mid // ac + mid // abc: O(1)
• Comparison with n: O(1)

Since all operations inside the loop are O(1) and the loop runs O(log m) times, the overall time complexity is O(log m).

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store:

• Variables ab, bc, ac, abc for the least common multiples
• Variables l, r, mid for the binary search bounds and midpoint
• The comparison result

All these variables require constant space regardless of the input size n, making the space complexity O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

A common mistake is using while left < right with right = mid instead of the standard template with while left <= right, first_true_index, and right = mid - 1.

Problem Example:

# Non-standard variant - harder to reason about
while left < right:
    mid = (left + right) // 2
    if count >= n:
        right = mid
    else:
        left = mid + 1
return left

Solution:

# Standard template - clear and consistent
first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

2. Integer Overflow in LCM Calculation

The most critical pitfall is calculating LCM using the formula lcm(x, y) = x * y / gcd(x, y). When x and y are large, their product can overflow.

Problem Example:

# Incorrect - multiplication happens first, can overflow
def lcm(x, y):
    return x * y // gcd(x, y)  # x * y might overflow before division

Solution:

# Better - divide first to reduce overflow risk
def lcm(x, y):
    return x // gcd(x, y) * y  # Divide first, then multiply

3. Incorrect Order of LCM Calculations for Three Numbers

When calculating lcm(a, b, c), a common mistake is assuming it equals a * b * c / gcd(a, b, c).

Problem Example:

# Incorrect approaches
lcm_abc = a * b * c // gcd(gcd(a, b), c)  # Wrong formula

Solution:

# Correct - LCM is associative
lcm_abc = lcm(lcm(a, b), c)

4. Forgetting Edge Cases in Inclusion-Exclusion

Not handling the case where some of the numbers (a, b, c) might be equal or one divides another, leading to incorrect LCM calculations or double counting.

Solution: The provided code handles this correctly by using proper LCM calculation with GCD, which automatically handles cases where numbers share common factors.

5. Using Wrong Binary Search Range

Setting an insufficient upper bound for the binary search can cause the answer to be outside the search range.

Solution:

# Safe upper bound per problem constraints
right = 2 * 10**9