1201. Ugly Number III

Problem

Write a program to find the n-th ugly number.

Ugly numbers are positive integers which are divisible by a or b or c.

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... The 3rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

Example 4:

Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984

Constraints:

• 1 <= n, a, b, c <= 10^9
• 1 <= a * b * c <= 10^18
• It's guaranteed that the result will be in range [1, 2 * 10^9]

Problem Summary

Please help design a program to find the nth ugly number. Ugly numbers are positive integers that can be divided by a or b or c.

Notes:

• 1 <= n, a, b, c <= 10^9
• 1 <= a * b * c <= 10^18
• The result of this problem is within the range [1, 2 * 10^9]

Solution Approach

• Given 4 numbers, a, b, c, and n. The task is to output the nth number that is divisible by a, or divisible by b, or divisible by c.
• This problem limits the range of the answer to [1, 2 * 10^9], so we can directly use binary search to solve it. Gradually narrow down to the low value until finding the minimum low that satisfies the condition, which is the final answer.
• The key to this problem is how to determine the rank of a number. If a number is divisible by a, divisible by b, and divisible by c, then it should be the num/a + num/b + num/c - num/ab - num/bc - num/ac + num/abcth number. This is the Venn diagram principle. Note that when calculating ab, bc, ac, and abc, you also need to divide by their respective greatest common divisor gcd().

Code

package leetcode

func nthUglyNumber(n int, a int, b int, c int) int {
	low, high := int64(0), int64(2*1e9)
	for low < high {
		mid := low + (high-low)>>1
		if calNthCount(mid, int64(a), int64(b), int64(c)) < int64(n) {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return int(low)
}

func calNthCount(num, a, b, c int64) int64 {
	ab, bc, ac := a*b/gcd(a, b), b*c/gcd(b, c), a*c/gcd(a, c)
	abc := a * bc / gcd(a, bc)
	return num/a + num/b + num/c - num/ab - num/bc - num/ac + num/abc
}

func gcd(a, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}