Ugly Number III - Video Solutions

Problem Overview: You need to find the nth positive integer that is divisible by at least one of three numbers a, b, or c. These are called ugly numbers for this problem. The challenge is that n can be as large as 10^9, so generating numbers one by one is not feasible.

Approach 1: Priority Queue (Min-Heap) Simulation (Time: O(n log k), Space: O(n))

This method simulates the generation of ugly numbers using a min-heap. Start by pushing a, b, and c into the heap and repeatedly extract the smallest value while pushing the next multiples. A set or duplicate-check is required because many numbers appear through multiple paths (for example, 6 from both 2×3 and 3×2). The heap always keeps the smallest candidate on top, so extracting the minimum n times yields the answer. This approach demonstrates the idea clearly but becomes slow when n is large.

Approach 2: Binary Search with Inclusion-Exclusion Principle (Time: O(log R), Space: O(1))

The optimal solution uses binary search combined with the inclusion-exclusion principle from math and number theory. Instead of generating ugly numbers, search for the smallest integer x such that at least n numbers ≤ x are divisible by a, b, or c.

To count how many valid numbers are ≤ x, compute:

count = x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c)

This formula avoids double-counting numbers divisible by multiple values. The lcm values are derived using lcm(a,b) = a * b / gcd(a,b). During binary search, if the count is at least n, move the right boundary left; otherwise move the left boundary right. The search space ranges up to about 2 × 10^9, so the algorithm runs in roughly O(log R) iterations with constant work per step.

Recommended for interviews: Interviewers expect the binary search + inclusion-exclusion solution. The heap simulation shows you understand how ugly numbers could be generated, but it does not scale to the constraints. The optimal approach demonstrates strong understanding of counting techniques, LCM/GCD math, and binary search on the answer, which are common patterns in medium-to-hard algorithm problems.