Sponsored
Sponsored
This approach leverages binary search to efficiently find the nth magical number by examining the number of magical numbers <= mid value repeatedly until we find the nth one. Calculating the Least Common Multiple (LCM) of 'a' and 'b' helps in determining magical numbers.
Time Complexity: O(log(N * min(a, b)))
Space Complexity: O(1)
1using System;
2
3class Solution {
4 public int NthMagicalNumber(int n, int a, int b) {
5 long MOD = 1000000007;
6 long left = 2, right = (long)n * Math.Min(a, b);
7 long lcm_ab = LCM(a, b);
8
9 while (left < right) {
10 long mid = left + (right - left) / 2;
11 if (CountMagicalNumbers(a, b, lcm_ab, mid) < n) {
12 left = mid + 1;
13 } else {
14 right = mid;
15 }
16 }
17 return (int)(left % MOD);
18 }
19
20 private long GCD(long a, long b) { return b == 0 ? a : GCD(b, a % b); }
21
22 private long LCM(long a, long b) { return a / GCD(a, b) * b; }
23
24 private long CountMagicalNumbers(long a, long b, long lcm, long x) {
25 return x / a + x / b - x / lcm;
26 }
27}
28
29class Program {
30 static void Main() {
31 Solution sol = new Solution();
32 Console.WriteLine(sol.NthMagicalNumber(4, 2, 3));
33 }
34}
35The C# solution is built using a class to encapsulate the measure of nth magical number which makes it structured and reusable. The helper methods for GCD, LCM, and counting follow straightforward logic to enable an efficient binary search on the given constraints in the problem statement.
This approach involves generating magical numbers using a min-heap to simulate the generation process by pushing candidates generated by multiplying a set of base magical numbers with 'a' and 'b'. The minimum is repeatedly extracted until the nth magical number is found.
Time Complexity: O(n log n)
Space Complexity: O(n)
1import heapq
2
3def nthMagicalNumber(n, a, b):
4
The Python implementation uses a min-heap to manage and produce candidates for the magical numbers by systematically adding increments of 'a' and 'b'. The heap automatically keeps this collection sorted with respect to numerical magnitude, achieving efficient extraction. It ensures that duplicates (i.e., the same number coming from both sequences) are managed via conditions if a number is divisible by the increment.