Nth Magical Number

class Solution {
public:
    int findNthMagicNumber(int position, int first, int second) {
        int modulo = 1000000007;
        int leastCommonMultiple = first / greatestCommonDivisor(first, second) * second;
    
        long low = 0;
        long high = (long)position * std::min(first, second);
        while (low < high) {
            long mid = low + (high - low) / 2;
            if (mid / first + mid / second - mid / leastCommonMultiple < position)
                low = mid + 1;
            else
                high = mid;
        }
    
        return (int)(low % modulo);
    }
    
    int greatestCommonDivisor(int a, int b) {
        if (a == 0) return b;
        return greatestCommonDivisor(b % a, a);
    }
};

This C++ solution implements a function to find the Nth magical number. A magical number is defined as a positive integer that is divisible by either of two given numbers. The solution uses binary search to efficiently find the desired magical number, leveraging mathematical principles such as the greatest common divisor (GCD) and least common multiple (LCM).

• Calculation of LCM: Computes the least common multiple using the formula LCM(a, b) = a / GCD(a, b) * b, ensuring that the calculation handles potential overflows by dividing before multiplying.
• Binary Search Approach:
  • Establishes a search range from 0 to position * min(first, second).
  • Uses a binary search to find the smallest number such that the count of magical numbers up to that point is at least the desired position.
• Result Normalization: The result is modulo 1000000007 to ensure it fits within typical integer type limits and to comply with constraints that are often set in programming contests or systems.

Function Implementation:

• findNthMagicNumber() main function for finding the Nth magical number and modulo operation to conform with constraints.
• greatestCommonDivisor(), a helper function necessary for the LCM calculation, implemented recursively.

This approach ensures that the time complexity is reduced compared to a direct computation method, which would be inefficient for large inputs. The use of fundamental number theory concepts like GCD and LCM is critical for optimizing the solution's efficiency.

class Solution {
    public int findNthMagicalNumber(int N, int X, int Y) {
        int MODULO = 1_000_000_007;
        int lcmValue = X / calculateGCD(X, Y) * Y;
    
        long low = 0;
        long high = (long) N * Math.min(X, Y);
        while (low < high) {
            long mid = low + (high - low) / 2;
            if (mid / X + mid / Y - mid / lcmValue < N)
                low = mid + 1;
            else
                high = mid;
        }
    
        return (int) (low % MODULO);
    }
    
    private int calculateGCD(int a, int b) {
        if (a == 0) return b;
        return calculateGCD(b % a, a);
    }
}

The provided Java solution computes the Nth magical number where a number is considered magical if it is divisible by either of two given positive integers X or Y.

Here’s a breakdown of the solution:

• Define the findNthMagicalNumber method which takes three parameters: N (the Nth magical number to find), X, and Y.

• An integer MODULO is introduced to ensure the result remains within the bounds of integer values typically used in programming contests.

• Calculate the least common multiple (LCM) of X and Y using the GCD method, leveraging the relationship LCM(X, Y) = (X * Y) / GCD(X, Y). This is used to adjust for numbers that are counted twice (divisible by both X and Y).

• Implement a binary search between 0 and N * min(X, Y). The upper bound assumes the worst-case scenario with the smallest among X and Y.

• During each iteration of the binary search, set the mid-value and calculate the magical numbers up to mid using the formula: (mid / X) + (mid / Y) - (mid / lcmValue). Adjust the low and high pointers based on whether the current mid-value produces fewer than N magical numbers.

• Return the smallest number that has exactly N numbers less than it that are multiples of either X or Y, modulated by 1_000_000_007 to ensure it fits within typical bounds.

The helper method calculateGCD uses the Euclidean algorithm to recursively find the greatest common divisor (GCD), which is essential for finding the LCM.

This solution efficiently finds the Nth magical number using mathematical properties and logarithmic searching—returning results in optimal time for large inputs.

var magicalNumberAtIndex = function(index, first, second) {
    const computeGCD = (num1, num2) => {
        if (num1 == 0) return num2;
        return computeGCD(num2 % num1, num1);
    }
    
    const MODULO = 1000000007;
    const LCM = first / computeGCD(first, second) * second;
    
    let lowerBound = 0;
    let upperBound = index * Math.min(first, second);
    while (lowerBound < upperBound) {
        let middle = lowerBound + Math.trunc((upperBound - lowerBound) / 2);
        // Check if the count of magical numbers below middle is less than index
        if (Math.trunc(middle/first) + Math.trunc(middle/second) - Math.trunc(middle/LCM) < index)
            lowerBound = middle + 1;
        else
            upperBound = middle;
    }
    
    return lowerBound % MODULO;
};

In the JavaScript solution to the problem of finding the Nth magical number, the approach utilizes binary search and number theory concepts such as Greatest Common Divisor (GCD) and Least Common Multiple (LCM). Here's how the solution works:

• GCD Calculation: The solution defines an inner function computeGCD to compute the Greatest Common Divisor of two numbers using Euclid's algorithm. This helps in determining the LCM.

• LCM Computation: Using the calculated GCD, the solution then computes the Least Common Multiple of the two given numbers. The formula used is ( \text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)} ).

• Utilizing Binary Search: To find the Nth magical number, the solution employs binary search. The search space spans from 0 to ( \text{index} \times \min(\text{first}, \text{second}) ).

• Binary Search Implementation:

  1. It initializes the lowerBound to zero and upperBound to ( \text{index} \times \min(\text{first}, \text{second}) ).

  2. The loop continues until lowerBound is not less than upperBound.

  3. On each iteration, the middle point is calculated, and the count of magical numbers below this midpoint is determined by considering individual counts from both numbers and adjusting for overlaps using the LCM.

  4. If the number of magical numbers below the midpoint is less than the desired index, the search space is adjusted to explore higher numbers by setting lowerBound to middle + 1. Otherwise, upperBound becomes middle.

• Returning the Result: The final result is obtained by taking the modulo of lowerBound with (10^9 + 7), ensuring that the solution handles very large output gracefully.

This efficient method ensures that the Nth magical number is found in a logarithmic time complexity relative to the search bounds, making it apt for large inputs.