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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Nth Magical Number

Number: 910

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given three integers n, a, and b, a magical number is defined as a positive integer divisible by a or b. The goal is to find the nth magical number, where the answer is required modulo 10^9 + 7.

Key Insights

  • The problem involves counting numbers divisible by either a or b, which can be done using the inclusion-exclusion principle.
  • Use binary search to efficiently find the smallest number x such that the count of magical numbers up to x is at least n.
  • The count function is: count(x) = x//a + x//b - x//lcm(a, b), where lcm(a, b) is the least common multiple of a and b.
  • Since n can be very large (up to 10^9), binary search is essential to avoid iterating over a large range.

Space and Time Complexity

Time Complexity: O(log(n * min(a, b))), due to binary search over the range. Space Complexity: O(1), as only a constant amount of extra space is used.

Solution

The solution starts by computing the least common multiple (LCM) of a and b using the greatest common divisor (GCD). A binary search is then performed over a potential range [1, n * min(a, b)] to find the smallest number x such that the number of magical numbers ≤ x (calculated using the inclusion-exclusion principle) is at least n. After finding x, we return x modulo 10^9 + 7 to handle potentially large numbers.

Code Solutions

# Python solution with explanatory comments

import math

def nthMagicalNumber(n, a, b):
    # Define the module constant
    mod = 10**9 + 7
    # Compute the least common multiple (LCM) of a and b using the GCD
    lcm = a * b // math.gcd(a, b)
    
    # Initialize binary search boundaries:
    # 'low' is the minimum magical number, and 
    # 'high' is set to n multiplied by the smaller of a and b.
    low, high = 1, n * min(a, b)
    
    # Binary search to find the smallest number x with count(x) >= n.
    while low < high:
        mid = (low + high) // 2
        # Count numbers divisible by a or b up to mid using inclusion-exclusion.
        count = mid // a + mid // b - mid // lcm
        # If count is less than n, move the lower bound up.
        if count < n:
            low = mid + 1
        else:
            high = mid
    # Return the magical number modulo 10^9 + 7.
    return low % mod

# Example usage:
# print(nthMagicalNumber(4, 2, 3))
← Back to All Questions