MediumCoding

Ugly Number III

Asked at

Media.net

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Binary search the candidate value x.
02Count numbers up to x divisible by a, b, or c.
03Use inclusion-exclusion with gcd-based LCMs.
04Find the first x whose count reaches n.

Reference answer

Ugly Number III asks for the nth positive integer divisible by at least one of a, b, or c. The predicate “there are at least n qualifying numbers up to x” is monotone, so binary-search x. Count qualifying values with inclusion-exclusion: x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c). Compute each LCM as u/gcd(u,v)*v using a wide integer and cap it above the search bound to avoid overflow. Search from one to a safe upper bound such as n*min(a,b,c) in 64-bit arithmetic, returning the first x with count at least n. Complexity is O(log upperBound * log max(a,b,c)) due to gcd calls, with O(1) space. Test overlapping divisors and equal divisors.

Then expect these follow-ups

Why is the count predicate monotone?
Tests: binary search proof
How do you cap an overflowing LCM?
Tests: integer safety

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question