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 binary search 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: Set up Binary Search Boundaries

• Left boundary l = 1 (smallest possible ugly number)
• Right boundary r = 2 × 10^9 (maximum value per problem constraints)

Step 3: Binary Search Loop While l < r:

1. Calculate midpoint: mid = (l + r) >> 1 (using bit shift for division by 2)
2. Count ugly numbers up to mid using inclusion-exclusion:

   count = mid//a + mid//b + mid//c - mid//ab - mid//bc - mid//ac + mid//abc

3. Make decision based on count:
   • If count >= n: The n-th ugly number is at most mid, so search in left half: r = mid
   • If count < n: We need more ugly numbers, so search in right half: l = mid + 1

Step 4: Return Result When the loop ends, l equals r, which is the smallest number x such that there are exactly n ugly numbers less than or equal to x. This is our answer.

Why this works:

• The binary search maintains an invariant: the answer is always in the range [l, r]
• We're looking for the leftmost position where the count is at least n
• When count >= n at mid, we include mid in our search range (r = mid) because mid itself might be the n-th ugly number
• When count < n, we exclude mid (l = mid + 1) because we need a larger number

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. 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 even in languages with large integer support, or cause precision issues.

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

2. Incorrect Order of LCM Calculations for Three Numbers

When calculating lcm(a, b, c), a common mistake is treating it as lcm(a, lcm(b, c)) or 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
lcm_abc = lcm(a, b * c)  # Conceptually wrong

Solution:

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

3. Off-by-One Error in Binary Search Boundary

Setting the wrong condition for the binary search loop or incorrect boundary updates can lead to infinite loops or wrong answers.

Problem Example:

# Incorrect - might miss the answer
while left <= right:  # Using <= instead of <
    mid = (left + right) // 2
    if count >= n:
        right = mid - 1  # Wrong: excludes potential answer
    else:
        left = mid + 1

Solution:

# Correct - maintains answer in [left, right]
while left < right:
    mid = (left + right) // 2
    if count >= n:
        right = mid  # Keep mid as potential answer
    else:
        left = mid + 1

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.

Problem Example:

# If a = 2, b = 4, c = 6
# lcm(2, 4) = 4, not 8
# Need to ensure correct LCM calculation

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.

Problem Example:

# Incorrect - might be too small for large n
right = n * max(a, b, c)  # Could underestimate for certain inputs

Solution:

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