Nth Magical Number - Leetcode Solution

Problem Statement:

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.

Input: N = 1, A = 2, B = 3 Output: 2 Explanation: A or B divides 2.

Input: N = 4, A = 2, B = 3 Output: 6 Explanation: The magical numbers are {2, 3, 4, 6}, so the 4th magical number is 6.

Input: N = 5, A = 2, B = 4 Output: 10 Explanation: The magical numbers are {2, 4, 6, 8, 10}, so the 5th magical number is 10.

Approach:

The first thing that comes to our mind is Brute Force. We can start from 1, and check if each number is magical or not. We can stop whenever we reach the Nth magical number. This method is highly inefficient because the time complexity would be O(N * max(A,B)). Given the constraints, it would certainly fail.

Hence we have to come up with an alternative approach. We can use Binary Search to find the answer. The range for our search should be like this: Between 1 and max(A, B) times N. Why? Because the Nth magical number must be between this range.

Algorithm:

1. We will set minimum and maximum limits for binary search between 1 and max(A, B) * N, i.e., left = 1, right = N * max(A, B).

2. In each iteration of your binary search, we will take the middle element of our search space as mid = (left + right) / 2.

3. We will count the number of magical numbers up to this value mid. For that, we will use LCM (Least Common Multiple) operation.

4. If the count is less than the required N, we know that the Nth magical number must be greater than or equal to mid. Therefore, we will update left = mid + 1.

5. If the count is greater than or equal to N, we know that the Nth magical number must be less than or equal to mid. Therefore, we will update right = mid.

6. We repeat step 2 to 5 until we find the Nth magical number.

Code:

int nthMagicalNumber(int N, int A, int B) { int mod = 1e9 + 7; int left = 1, right = N * max(A, B); long long ab = (long long) A * B; while (left < right) { int mid = (left + right) / 2; long long count = mid / A + mid / B - mid / ab; if (count < N) left = mid + 1; else right = mid; } return left % mod; }

Time Complexity: O(log(A * B) * log(N)).

Space Complexity: O(1).

1