Problem Description

A positive integer is considered magical if it is divisible by either A or B. The task is to return the N-th magical number. The answer could be very large and hence the output should be the value modulo 10^9 + 7.

For example, consider N= 4, A= 2, and B= 3. The first four magical numbers divisible by 2 or 3 are 2, 3, 4, and 6. Hence the N-th (4th) magical number is 6.

Solution Approach

The solution uses the binary search method to find the N-th magical number. This is combined with the method for finding the least common multiple.

We start by setting the least common multiple (lcm) of A and B. This is given by the formula lcm = a * b / gcd(a, b) where gcd is the greatest common divisor of A and B.

Next, we do binary search between the minimum of a and b (left limit 'l') and that minimum times n (right limit 'r').

Our goal is to figure out a value m (mid-point of l and r) such that it satisfies the condition m / a + m / b - m / lcm >= n. The quantities m/a and m/b represent numbers which can be divisible by a and b up to m. The term m/lcm subtracts the over-counting.

As long as the left limit is less than the right limit, we continue to find the mid-point m, and adjust our limits based on the condition. If the condition is met, we set the right limit to m, else we set the left limit to m + 1.

At the end of binary search, the left limit will be the N-th magical number.

Java Solution

1
2java=
3public class Solution {
4    public int nthMagicalNumber(long n, long a, long b) {
5        int mod = 1_000_000_007;
6        long lcm = a * b / gcd(a, b);
7        long left = Math.min(a, b);
8        long right = Math.min(a, b) * n;
9
10        while (left < right) {
11            long mid = (left + right) / 2;
12            if (mid / a + mid / b - mid / lcm >= n)
13                right = mid;
14            else
15                left = mid + 1;
16        }
17
18        return (int)(left % mod);
19    }
20    
21    private long gcd(long a, long b) {
22        if(b == 0)
23            return a;
24        return gcd(b, a % b);
25    }
26}

Python Solution

1
2python
3class Solution:
4    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
5        from math import gcd
6        lcm = a * b // gcd(a, b)
7        l, r = min(a, b), min(a, b) * n
8        mod = 10**9 + 7
9
10        while l < r:
11            m = (l + r) >> 1
12            if m // a + m // b - m // lcm >= n:
13                r = m
14            else:
15                l = m + 1
16
17        return l % mod

JavaScript Solution

1
2javascript
3class Solution {
4    nthMagicalNumber(N, A, B) {
5        const MOD = 1e9 + 7;
6        const LCM = A * B / gcd(A, B);
7        let lo = 0;
8        let hi = 1e14;
9        while (lo < hi) {
10            let mi = lo + Math.floor((hi - lo) / 2);
11            if (Math.floor(mi / A) + Math.floor(mi / B) - Math.floor(mi / LCM) < N)
12                lo = mi + 1;
13            else
14                hi = mi;
15        }
16
17        return lo % MOD;
18        
19        function gcd(a, b) {
20            let t;
21            while (b !== 0) {
22                t = b;
23                b = a % b;
24                a = t;
25            }
26            return a;
27        }
28    }
29}
30
31let sol = new Solution();

C# Solution

1
2csharp
3public class Solution {
4    public int nthMagicalNumber(long N, long A, long B) {
5        long mod = (long)1e9 + 7, l = 2, r = (long)1e14, lcm = A * B / Gcd(A, B);
6        while (l < r) {
7            long m = (l + r) / 2;
8            if (m / A + m / B - m / lcm < N) l = m + 1;
9            else r = m;
10        }
11        return (int)(l % mod);
12    }
13
14    private long Gcd(long a, long b)
15    {
16        if (b == 0) return a;
17        return Gcd(b, a % b);
18    }
19}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int nthMagicalNumber(int n, int a, int b) {
6        const int kMod = 1'000'000'007;
7        long lcm = a * b / gcd(a, b);
8        long l = min(a, b);
9        long r = min(a, b) * n;
10
11        while (l < r) {
12            const long m = (l + r) / 2;
13            if (m / a + m / b - m / lcm >= n)
14                r = m;
15            else
16                l = m + 1;
17        }
18
19        return l %= kMod;
20    }
21};

Conclusion

In this article, we discussed the problem of finding the N-th magical number, which is described as a number divisible by either of the two given numbers A or B.

We explained a binary search-based approach to solve this problem, making use of the concept of least common multiple (LCM) and greatest common divisor (GCD).

This problem serves as a great opportunity to practice your binary search algorithm understanding and implementation, along with applications of concepts from number theory like LCM and GCD. We have provided the solution in multiple programming languages including Java, Python, JavaScript, C# and C++, thus catering to a diverse group of readers.

Your understanding and proficiency in these concepts, alongside efficient algorithm creation, play an important role not just in problem-solving on online programming platforms, but also in real-world software development scenarios. We hope this session was instructive to you. Keep practicing and happy coding!