Solution For Nth Magical Number

Problem Statement:

A positive integer is magical if it is divisible by either A or B.

Return the N-th magical number. Since the answer may be very large, return it modulo 10^9 + 7.

Input: N = 1, A = 2, B = 3
Output: 2
Explanation: A or B divides 2.

Input: N = 4, A = 2, B = 3
Output: 6
Explanation: The magical numbers are {2, 3, 4, 6}, so the 4th magical number is 6.

Input: N = 5, A = 2, B = 4
Output: 10
Explanation: The magical numbers are {2, 4, 6, 8, 10}, so the 5th magical number is 10.

Approach:

The first thing that comes to our mind is Brute Force. We can start from 1, and check if each number is magical or not. We can stop whenever we reach the Nth magical number. This method is highly inefficient because the time complexity would be O(N * max(A,B)). Given the constraints, it would certainly fail.

Hence we have to come up with an alternative approach. We can use Binary Search to find the answer. The range for our search should be like this: Between 1 and max(A, B) times N. Why? Because the Nth magical number must be between this range.

Algorithm:

1. We will set minimum and maximum limits for binary search between 1 and max(A, B) * N, i.e., left = 1, right = N * max(A, B).
2. In each iteration of your binary search, we will take the middle element of our search space as mid = (left + right) / 2.
3. We will count the number of magical numbers up to this value mid. For that, we will use LCM (Least Common Multiple) operation.
4. If the count is less than the required N, we know that the Nth magical number must be greater than or equal to mid. Therefore, we will update left = mid + 1.
5. If the count is greater than or equal to N, we know that the Nth magical number must be less than or equal to mid. Therefore, we will update right = mid.
6. We repeat step 2 to 5 until we find the Nth magical number.

Code:

int nthMagicalNumber(int N, int A, int B) {
int mod = 1e9 + 7;
int left = 1, right = N * max(A, B);
long long ab = (long long) A * B;
while (left < right) {
int mid = (left + right) / 2;
long long count = mid / A + mid / B – mid / ab;
if (count < N)
left = mid + 1;
else
right = mid;
}
return left % mod;
}

Time Complexity: O(log(A * B) * log(N)).

Space Complexity: O(1).

Step by Step Implementation For Nth Magical Number

/*

Solution for the leetcode problem "nth-magical-number"

*/



public class Solution {

public int nthMagicalNumber(int N, int A, int B) {
        
        //calculate the lcm of A and B
        int lcm = A * B / gcd(A, B);
        
        //binary search to find the smallest number that is divisible by A or B and is also greater than or equal to N
        int left = 0;
        int right = N * lcm;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid / A + mid / B - mid / lcm < N) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left % 1000000007;
    }
    
    //Euclidean algorithm to calculate the greatest common divisor of two numbers
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

A magical number is a positive integer whose sum of digits is the product of digits. 

Given an integer N, return the N-th magical number. If it doesn't exist, return -1.

Note: N will not exceed 100,000.

def nthMagicalNumber(N, A, B):

# This function finds the N-th magical number 
# A and B are the two given integers 
# N is the number we have to find 

# We use the concept of binary search to find the number 

# First we find the least possible value of the number 
# which is nothing but the LCM of A and B 

lcm = (A * B) // math.gcd(A, B)

# We define two variables left and right 
# which defines the range in which we have to search 

left = 0
right = lcm * N

# We run a loop until left is less than right 

while left < right: 
	
	# We find the mid value 
	mid = (left + right) // 2

	# We find the number of integers between A and B 
	# which are divisible by the LCM of A and B 
	# using the formula (r1 - l1 + 1) + (r2 - l2 + 1) - 1 

	num = (mid // A) + (mid // B) - (mid // lcm)

	# We compare the number with N 
	# If the number is less than N 
	# we move to the right side 
	# else we move to the left side 

	if num < N: 
		left = mid + 1
	else: 
		right = mid 

# After the loop ends 
# left will have the required answer 

return left % (1000000000 + 7)

/*

Problem:

Given two integers n and m, find the nth magical number.

A magical number is a positive integer that is divisible by either A or B.

Example 1:

Input: n = 2, m = 3
Output: 4
Explanation: The magical numbers are [1, 2, 3, 4]. Note that 4 is nth magical number, since it is (2 * 2) and also (3 * 1).

Example 2:

Input: n = 5, m = 2
Output: 10
Explanation: The magical numbers are [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Note that 10 is the nth magical number, since it is (5 * 2) and also (2 * 5).



Solution:

We can use a brute force approach to find the nth magical number.

We start with a number 1 and keep incrementing it until we find the nth magical number.

We can use a helper function to check if a number is magical.

*/

function isMagical(num, A, B) {
    return num % A === 0 || num % B === 0;
}

function nthMagicalNumber(n, A, B) {
    let num = 1;
    let count = 0;
    
    while (count < n) {
        if (isMagical(num, A, B)) {
            count++;
        }
        
        if (count === n) {
            return num;
        }
        
        num++;
    }
}

A magical number is a positive integer that is divisible by either A or B.

Given A, B and N, write a function to return the N-th magical number.

For example, given A = 2, B = 3, N = 4, the function should return 6, as the first 4 magical numbers are: 2, 3, 4, 6.

Note:

1. N will not exceed 100,000.
2. A and B are integers within the range [1, 30,000].

int nthMagicalNumber(int A, int B, int N) {
        long long l = 0, r = 2e9, mid, ans;
        int g = __gcd(A, B);
        while(l <= r) {
            mid = l + (r - l) / 2;
            if((mid/A + mid/B - mid/g) >= N) {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        return ans % (int)(1e9 + 7);
    }

using System; 

public class Solution { 

public int NthMagicalNumber(int N, int A, int B) { 

// TODO: Implement your solution here 

} 

}