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.
- Difficulty: Medium
- Topics: Math, Binary Search, Number Theory, Combinatorics
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^91 <= a * b * c <= 10^18The answer lies in [1, 2 * 10^9]
Hints for Ugly Number III
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?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).Hint 3
The count never decreases as
xgrows, so binary search for the smallestxwhose count reachesn. 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
- Precompute
lcm(a,b),lcm(a,c),lcm(b,c)andlcm(a,b,c)usinglcm(x,y) = x / gcd(x,y) * y; any lcm above2·10^9can be replaced by a cap just above that, since it divides no candidate. - 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). - Binary search
xin[1, 2·10^9]for the smallest value withcount(x) >= n, using 64-bit arithmetic. - 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 andlcm(a,b) * ccan overflow 64 bits — cap each lcm once it exceeds the search range.- Using the smallest
xwithcount(x) == ncan land on a non-ugly number; search for>= nand take the lower bound. lo + hiexceeds 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 loJava
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