878. Nth Magical Number #

Problem #

A positive integer is magical if it is divisible by either A or B.

Return the N-th magical number. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: N = 1, A = 2, B = 3
Output: 2

Example 2:

Input: N = 4, A = 2, B = 3
Output: 6

Example 3:

Input: N = 5, A = 2, B = 4
Output: 10

Example 4:

Input: N = 3, A = 6, B = 4
Output: 8

Note:

1. 1 <= N <= 10^9
2. 2 <= A <= 40000
3. 2 <= B <= 40000

Problem Summary #

If a positive integer can be divided by A or B, then it is magical. Return the N-th magical number. Since the answer may be very large, return the result modulo 10^9 + 7.

Notes:

1. 1 <= N <= 10^9
2. 2 <= A <= 40000
3. 2 <= B <= 40000

Solution Ideas #

• Given 3 numbers, a, b, and n. It is required to output the n-th number that is divisible by a or divisible by b.
• This problem is a reduced version of Problem 1201. The code and solution idea are basically unchanged. The binary search interval for this problem is [min(A, B)，N * min(A, B)] = [2, 10 ^ 14]. The other code is the same as Problem 1201; see Problem 1201 for the idea.

Code #

package leetcode

func nthMagicalNumber(N int, A int, B int) int {
	low, high := int64(0), int64(1*1e14)
	for low < high {
		mid := low + (high-low)>>1
		if calNthMagicalCount(mid, int64(A), int64(B)) < int64(N) {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return int(low) % 1000000007
}

func calNthMagicalCount(num, a, b int64) int64 {
	ab := a * b / gcd(a, b)
	return num/a + num/b - num/ab
}