Ugly Number III

Medium
1291.

Ugly Number III

Ugly Number III is a medium coding problem on math, binary search and number theory, asked in Amazon and Google interviews.

Call a positive integer ugly if it is divisible by a, by b or by c (at least one of them).

Return the n-th ugly number, counting from 1 in increasing order.

Example 1

Input
n = 3, a = 2, b = 3, c = 5
Output
4
Explanation
The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10, … and the third is 4.

Example 2

Input
n = 4, a = 2, b = 3, c = 4
Output
6
Explanation
2, 3, 4, 6, 8, 9, … — 4 and 8 are counted once even though both 2 and 4 divide them.

Example 3

Input
n = 5, a = 2, b = 11, c = 13
Output
10
Explanation
2, 4, 6, 8, 10, …

Constraints

  • 1 <= n, a, b, c <= 10^9
  • 1 <= a * b * c <= 10^18
  • The answer lies in [1, 2 * 10^9]
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var nthUglyNumber = function(n, a, b, c) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Ugly Number III — Solution in Python, Java & C++

Ugly Number III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Ugly Number III is a medium coding problem on math, binary search and number theory, asked in Amazon and Google interviews.

Problem statement

Call a positive integer ugly if it is divisible by a, by b or by c (at least one of them).

Return the n-th ugly number, counting from 1 in increasing order.

Example 1

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10, … and the third is 4.

Example 2

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: 2, 3, 4, 6, 8, 9, … — 4 and 8 are counted once even though both 2 and 4 divide them.

Example 3

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: 2, 4, 6, 8, 10, …

Constraints

  • 1 <= n, a, b, c <= 10^9
  • 1 <= a * b * c <= 10^18
  • The answer lies in [1, 2 * 10^9]

Hints for Ugly Number III

  1. Hint 1

    Generating the ugly numbers one by one can take 10^9 steps. Can you instead count how many ugly numbers are at most some value x?

  2. Hint 2

    By inclusion–exclusion that count is x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c) (integer divisions).

  3. Hint 3

    The count never decreases as x grows, so binary search for the smallest x whose count reaches n. Watch the lcms: they can exceed 64 bits only if you let them — cap them above 2 * 10^9.

How to solve Ugly Number III

Binary search on the answer, counting ugly numbers up to x with inclusion–exclusion over the three divisors.

Approach

  1. Precompute lcm(a,b), lcm(a,c), lcm(b,c) and lcm(a,b,c) using lcm(x,y) = x / gcd(x,y) * y; any lcm above 2·10^9 can be replaced by a cap just above that, since it divides no candidate.
  2. Define count(x) = x/a + x/b + x/c − x/lcm(a,b) − x/lcm(a,c) − x/lcm(b,c) + x/lcm(a,b,c).
  3. Binary search x in [1, 2·10^9] for the smallest value with count(x) >= n, using 64-bit arithmetic.
  4. Return that x.

Why it works

count(x) is the size of the union of the multiples of a, b and c up to x; inclusion–exclusion adds the three sets, removes the pairwise overlaps (multiples of the pairwise lcms) and adds back the triple overlap. The count is non-decreasing and jumps by one exactly at each ugly number, so the smallest x with count(x) >= n is itself ugly and is the n-th one.

Complexity

  • Time — O(log(2·10^9)) ≈ 31 steps, plus O(log) for the gcds
  • Space — O(1)

Pitfalls

  • lcm(a, b, c) can reach 10^18 and lcm(a,b) * c can overflow 64 bits — cap each lcm once it exceeds the search range.
  • Using the smallest x with count(x) == n can land on a non-ugly number; search for >= n and take the lower bound.
  • lo + hi exceeds 2^31 near the top of the range; use 64-bit integers in the search.

Reference solution

Python

from math import gcd

def nthUglyNumber(n: int, a: int, b: int, c: int) -> int:
    def lcm(x: int, y: int) -> int:
        return x // gcd(x, y) * y

    ab, ac, bc = lcm(a, b), lcm(a, c), lcm(b, c)
    abc = lcm(ab, c)

    def count(x: int) -> int:
        return x // a + x // b + x // c - x // ab - x // ac - x // bc + x // abc

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

Java

static long unGcd(long x, long y) {
    while (y != 0) {
        long t = x % y;
        x = y;
        y = t;
    }
    return x;
}

static long unLcm(long x, long y) {
    long l = x / unGcd(x, y) * y;
    return l > 2000000000L ? 2000000001L : l;
}

public static int nthUglyNumber(int n, int a, int b, int c) {
    long ab = unLcm(a, b), ac = unLcm(a, c), bc = unLcm(b, c), abc = unLcm(ab, c);
    long lo = 1, hi = 2000000000L;
    while (lo < hi) {
        long mid = (lo + hi) / 2;
        long cnt = mid / a + mid / b + mid / c - mid / ab - mid / ac - mid / bc + mid / abc;
        if (cnt >= n) hi = mid;
        else lo = mid + 1;
    }
    return (int) lo;
}

C++

static long long unGcd(long long x, long long y) {
    while (y != 0) {
        long long t = x % y;
        x = y;
        y = t;
    }
    return x;
}

static long long unLcm(long long x, long long y) {
    long long l = x / unGcd(x, y) * y;
    return l > 2000000000LL ? 2000000001LL : l;
}

int nthUglyNumber(int n, int a, int b, int c) {
    long long ab = unLcm(a, b), ac = unLcm(a, c), bc = unLcm(b, c), abc = unLcm(ab, c);
    long long lo = 1, hi = 2000000000LL;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        long long cnt = mid / a + mid / b + mid / c - mid / ab - mid / ac - mid / bc + mid / abc;
        if (cnt >= n) hi = mid;
        else lo = mid + 1;
    }
    return (int)lo;
}

JavaScript

var nthUglyNumber = function(n, a, b, c) {
    var CAP = 2000000001;
    var gcd = function(x, y) {
        while (y !== 0) {
            var t = x % y;
            x = y;
            y = t;
        }
        return x;
    };
    var lcm = function(x, y) {
        var l = x / gcd(x, y) * y;
        return l > 2000000000 ? CAP : l;
    };
    var ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c), abc = lcm(ab, c);
    var count = function(x) {
        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);
    };
    var lo = 1, hi = 2000000000;
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (count(mid) >= n) hi = mid;
        else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search