Solution


Approach 1: Mathematical

Intuition and Algorithm

Let's try to count to the -th magical number mathematically.

First, the pattern of magical numbers repeats. Let be the least common multiple of and . If is magical, then is magical, because (for example) and implies , and similarly if were the divisor.

There are magical numbers less than or equal to : of them are divisible by , of them are divisible by , and of them is divisible by both. So instead of counting one at a time, we can count by at a time.

Now, suppose (with ). The first numbers contain magical numbers, and within the next numbers we want to find more magical ones.

For this task, we can use brute force. The next magical number (less ) will either be or . If for example it is , then the next number will either be or , and so on.

If the -th such magical number is , then the final answer is . Care must also be taken in the case that is .

Complexity Analysis

  • Time Complexity: , assuming a model where integer math operations are . The calculation of q * L is . The calculation of the -th magical number after is which is .

  • Space Complexity: .


Intuition

The number of magical numbers less than or equal to is a monotone increasing function in , so we can binary search for the answer.

Algorithm

Say , the least common multiple of and ; and let be the number of magical numbers less than or equal to . A well known result says that , and that we can calculate the function . For more information on least common multiples and greatest common divisors, please visit Wikipedia - Lowest Common Multiple.

Then . Why? There are numbers that are divisible by , there are numbers divisible by , and we need to subtract the numbers divisible by and that we double counted.

Finally, the answer must be between and . Without loss of generality, suppose , so that it remains to show

as desired.

Afterwards, the binary search on is straightforward. For more information on binary search, please visit [LeetCode Explore - Binary Search].

Complexity Analysis

  • Time Complexity: .

  • Space Complexity: .


Analysis written by: @awice.