Code Implementation

import math

def nthUglyNumber(n, a, b, c):
    def count(x):
        # Inclusion-Exclusion Principle
        ab = a * b // math.gcd(a, b)
        ac = a * c // math.gcd(a, c)
        bc = b * c // math.gcd(b, c)
        abc = ab * c // math.gcd(ab, c)
        return x // a + x // b + x // c - x // ab - x // ac - x // bc + x // abc

    left, right = 1, 2 * 10 ** 9
    while left < right:
        mid = (left + right) // 2
        if count(mid) < n:
            left = mid + 1
        else:
            right = mid
    return left
      

#include <algorithm>
using namespace std;

class Solution {
public:
    typedef long long ll;
    ll gcd(ll a, ll b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    int nthUglyNumber(int n, int a, int b, int c) {
        ll ab = a * b / gcd(a, b);
        ll ac = a * c / gcd(a, c);
        ll bc = b * c / gcd(b, c);
        ll abc = ab * c / gcd(ab, c);
        auto count = [&](ll x) {
            return x / a + x / b + x / c - x / ab - x / ac - x / bc + x / abc;
        };
        ll left = 1, right = 2e9;
        while (left < right) {
            ll mid = left + (right - left) / 2;
            if (count(mid) < n)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};
      

class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        long ab = lcm(a, b);
        long ac = lcm(a, c);
        long bc = lcm(b, c);
        long abc = lcm(ab, c);
        long left = 1, right = 2000000000;
        while (left < right) {
            long mid = left + (right - left) / 2;
            long cnt = mid / a + mid / b + mid / c - mid / ab - mid / ac - mid / bc + mid / abc;
            if (cnt < n) left = mid + 1;
            else right = mid;
        }
        return (int)left;
    }
    private long lcm(long x, long y) {
        return x * y / gcd(x, y);
    }
    private long gcd(long x, long y) {
        while (y != 0) {
            long t = y;
            y = x % y;
            x = t;
        }
        return x;
    }
}
      

var nthUglyNumber = function(n, a, b, c) {
    function gcd(x, y) {
        return y === 0 ? x : gcd(y, x % y);
    }
    function lcm(x, y) {
        return x * y / gcd(x, y);
    }
    function count(x) {
        let ab = lcm(a, b);
        let ac = lcm(a, c);
        let bc = lcm(b, c);
        let abc = lcm(ab, c);
        return Math.floor(x / a) + Math.floor(x / b) + Math.floor(x / c)
            - Math.floor(x / ab) - Math.floor(x / ac) - Math.floor(x / bc)
            + Math.floor(x / abc);
    }
    let left = 1, right = 2e9;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (count(mid) < n) left = mid + 1;
        else right = mid;
    }
    return left;
};
      

Problem Description

Given four positive integers n, a, b, and c, find the nth positive integer that is divisible by at least one of a, b, or c. This number is called the "ugly number" in this context.

Key constraints:

• There is exactly one valid solution for each input.
• The ugly numbers are positive integers divisible by at least one of a, b, or c.
• Elements (numbers) are not reused; each ugly number is unique in its position.
• Input values can be large (up to 2 × 10⁹), so efficiency is important.

Thought Process

At first glance, the problem seems to invite a brute-force approach: check every number one by one, count how many are divisible by a, b, or c, and stop when you reach the nth such number. However, this is extremely inefficient for large values of n because you might need to check billions of numbers.

To optimize, we need to count efficiently how many numbers up to a given value are ugly numbers (divisible by a, b, or c). If we can quickly answer "How many ugly numbers ≤ X?", we can use binary search to find the smallest X such that this count is at least n.

The inclusion-exclusion principle is key here: it helps us count the total number of numbers divisible by any of the three values, without double-counting those divisible by more than one.

Solution Approach

• Step 1: Counting Ugly Numbers Up to X
  • For any number X, the count of numbers ≤ X divisible by a is X // a (integer division).
  • Similarly, X // b and X // c count those divisible by b and c.
  • However, numbers divisible by more than one of a, b, c are counted multiple times. We subtract the counts for each pair (e.g., X // lcm(a, b)), and add back in the count for all three (X // lcm(a, b, c)), using the inclusion-exclusion principle.
• Step 2: Binary Search for the Nth Ugly Number
  • Since ugly numbers are distributed monotonically (the count never decreases as X increases), we can use binary search.
  • Set left bound to 1, right bound to a large value (e.g., 2 × 10⁹).
  • For each midpoint, count how many ugly numbers are ≤ mid. If this is less than n, move left up. If greater or equal, move right down. Continue until left == right.
  • The answer is the smallest X such that the count is at least n.
• Step 3: Calculating LCM and GCD
  • We use greatest common divisor (GCD) to compute least common multiple (LCM), which is needed for inclusion-exclusion.
  • For example, lcm(a, b) = a * b // gcd(a, b).

This approach is efficient and avoids iterating over all numbers up to the answer.

Example Walkthrough

Example: n = 5, a = 2, b = 3, c = 4

• Find the 5th number that is divisible by 2, 3, or 4.
• The ugly numbers in order are:
  • 2 (divisible by 2)
  • 3 (divisible by 3)
  • 4 (divisible by 2 and 4)
  • 6 (divisible by 2 and 3)
  • 8 (divisible by 2 and 4)
• The 5th ugly number is 8.
• During binary search:
  • Try mid = 5: count(5) = 4 (not enough)
  • Try mid = 10: count(10) = 7 (too many)
  • Binary search narrows down to 8 as the smallest X with count(8) ≥ 5.

Time and Space Complexity

• Brute-force approach:
  • Time: O(n × (1/a + 1/b + 1/c)), but practically O(n) since we check each number up to the nth ugly number.
  • This is too slow for large n (up to 10⁹).
• Optimized approach (binary search + inclusion-exclusion):
  • Binary search over range up to 2 × 10⁹ takes O(log(maxX)) steps, where maxX is the right bound.
  • Each step computes the count in O(1) time (just arithmetic and GCD/LCM calculations).
  • Total time: O(log(maxX)) ≈ O(31) for 32-bit integers.
  • Space: O(1), since we use only a fixed number of variables.

Summary

The problem asks for the nth positive integer divisible by at least one of three given numbers. The elegant solution leverages the inclusion-exclusion principle to count ugly numbers up to any value efficiently, and binary search to zero in on the nth ugly number without checking every candidate. This approach is fast, uses constant space, and is robust even for very large inputs.