We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Nth Magical Number

Difficulty: Hard

Problem Description

A positive integer is magical if it is divisible by either a or b. Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 10^9 + 7.

Key Insights

  • A number is magical if it is divisible by a or b.
  • The nth magical number can be found using the Least Common Multiple (LCM) of a and b.
  • Binary search can be utilized to efficiently find the nth magical number.
  • The count of magical numbers up to any integer x can be computed as x // a + x // b - x // lcm(a, b).

Space and Time Complexity

Time Complexity: O(log(n * min(a, b)))
Space Complexity: O(1)

Solution

To find the nth magical number, we can use binary search. The approach involves:

  1. Define a function to compute the Least Common Multiple (LCM) of a and b.
  2. Use binary search to find the smallest integer x such that the count of magical numbers up to x is at least n.
  3. The count of magical numbers up to x can be calculated using the formula x // a + x // b - x // lcm(a, b).
  4. Return the result modulo 10^9 + 7.

Code Solutions

def nthMagicalNumber(n: int, a: int, b: int) -> int:
    MOD = 10**9 + 7
    
    def lcm(x, y):
        from math import gcd
        return x * (y // gcd(x, y))
    
    l = lcm(a, b)
    
    low, high = 1, n * min(a, b)
    while low < high:
        mid = (low + high) // 2
        if mid // a + mid // b - mid // l < n:
            low = mid + 1
        else:
            high = mid
            
    return low % MOD
← Back to All Questions