878. Nth Magical Number

Problem Description

The problem is about finding the nth number that is divisible by at least one of the two given numbers, a or b. These kinds of numbers are referred to as magical numbers. For instance, if a is 2 and b is 3, then the first few magical numbers would be 2, 3, 4 (divisible by 2), 6 (divisible by both 2 and 3), 8 (divisible by 2), and so on. The function nthMagicalNumber should return the nth magical number in this sequence.

However, due to the potentially large size of the output, we don't want the exact value of the nth magical number but instead its remainder when divided by 10^9 + 7, which is a commonly used large prime number in modular arithmetic problems to prevent integer overflow errors.

Intuition

When solving this problem, we need to consider a vital property of lcm (Least Common Multiple) of a and b, which will further help us understand the distribution of magical numbers. Specifically, every multiple of the lcm of a and b is a magical number which is also the least common period in which all the magical numbers repeat.

To arrive at the solution, we observe that:

Each multiple of a is a magical number.
Each multiple of b is a magical number.
Some numbers are multiples of both a and b, specifically multiples of the lcm of a and b.

We use a binary search to find the smallest number x where the count of magical numbers up to x is at least n. To count the number of magical numbers up to x, we sum up x // a (the count of multiples of a up to x), x // b (the count of multiples of b up to x), and subtract x // c (to account for over-counting the numbers that are multiples of both a and b, hence multiples of their lcm c).

The code exploits the bisect_left function from the bisect module to perform the binary search efficiently. It passes a virtual sequence up to r = (a + b) * n (an upper bound for the nth magical number) to bisect_left with a custom key function that calculates the aforementioned count. Then, it takes the result x of the binary search, which is essentially the nth magical number, and applies the modulo to maintain the result within the bounds required by the problem statement.

Learn more about Math and Binary Search patterns.

Solution Approach

The implementation of the solution includes the following concepts:

Binary Search: A classical algorithm to find the position of an element in a sorted array in logarithmic time complexity. Here, it is used to find the smallest number x such that there are at least n magical numbers less than or equal to x.
Least Common Multiple (LCM): Used to calculate the period at which the multiples of a and b repeat. This is critical, as we must adjust the counts to avoid counting any number more than once if it is divisible by both a and b.
Modular Arithmetic: This is used to avoid large number overflows by taking the modulus of the result with 10**9 + 7.
Efficient Counting: Using integer division to count multiples up to x for a, b, and their lcm.

Looking at the implementation step-by-step:

The mod variable is set to 10**9 + 7 to prepare for the final output to be given modulo this large prime.
The variable c calculates the lcm of a and b using a built-in lcm function (not shown in the snippet given, but can be implemented as the product of a and b divided by their greatest common divisor (gcd)).
The variable r defines an upper bound for the nth magical number, which can be set as the sum of a and b multiplied by n. This is based on the assumption that magical numbers will appear frequently enough that we do not need to check any number greater than this bound.
The magic happens with bisect_left(range(r), x=n, key=lambda x: x // a + x // b - x // c). This call is a bit unusual because it uses bisect_left on a range, leveraging the fact that Python ranges are lazy (they do not instantiate all values) and thus can be enormous without using much memory. The key function calculates the count of magical numbers up to x, and bisect_left will find the position where this count reaches at least n.
The % mod at the end of the function ensures the result is within the required modulus to prevent overflow and match the problem's constraints.

In summary, the code uses a binary search to efficiently find the nth magical number, leveraging knowledge of mathematical properties and algorithmic patterns to do so within the computing constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach with an example, let's choose a = 2, b = 3, and we want to find the 5th magical number.

Following the given solution approach:

Calculate the least common multiple (LCM) of a and b. The LCM of 2 and 3 is 6, because 6 is the smallest number that is divisible by both 2 and 3. Therefore, every 6 steps, the pattern of magical numbers will repeat.
We set an upper bound for the binary search. For n magical numbers, a rough upper bound would be (a+b) * n. In this case, (2+3)*5 = 25. Therefore, we can start our binary search from 1 to 25.
Use a binary search to find the smallest number x such that there are at least n magical numbers less than or equal to x. We do this by checking the count of multiples of a and b subtracted by the count of their LCM up to certain x. For each candidate number x, we calculate the count as x // a + x // b - x // c, where c is the LCM.
Suppose we test x = 10. To count the magic numbers up to 10, we find:
- Multiples of 2 up to 10: 10 // 2 = 5 (2, 4, 6, 8, 10).
- Multiples of 3 up to 10: 10 // 3 = 3 (3, 6, 9).
- Multiples of 6 up to 10: 10 // 6 = 1 (6).
Now we sum the counts of multiples of a and b then subtract the count of LCM of a and b: 5 + 3 - 1 = 7. This means there are 7 magical numbers up to 10. Since we are looking for the 5th magical number, 10 is an upper bound (too high) and we need to search lower.
Adjust the binary search range accordingly. Let's try x = 8. The calculations give us:
- Multiples of 2 up to 8: 8 // 2 = 4 (2, 4, 6, 8).
- Multiples of 3 up to 8: 8 // 3 = 2 (3, 6).
- Multiples of 6 up to 8: 8 // 6 = 1 (6).
Summing up and subtracting gives us 4 + 2 - 1 = 5. There are 5 magical numbers up to 8, so 8 is our candidate for the 5th magical number.
Repeat the binary search process until the range is narrowed down to a single number. Since we already found that there are 5 magical numbers up to 8 and we are looking for the 5th magical number, we can conclude that 8 is the 5th magical number.
Finally, we apply the modulo operation. Since the number is lower than 10**9 + 7, the modulus doesn't change the number. So the 5th magical number given a = 2 and b = 3 is 8.

This example demonstrates the binary search-based approach in a clear and step-by-step manner, following the key concepts outlined in the initial solution approach.

Solution Implementation

1from math import gcd
2from bisect import bisect_left
3
4class Solution:
5    def nth_magical_number(self, n: int, a: int, b: int) -> int:
6        # Define the modulo for the result as per the problem statement.
7        MOD = 10**9 + 7
8      
9        # Function to calculate the least common multiple (LCM).
10        def lcm(x, y):
11            return x * y // gcd(x, y)
12
13        # Calculate the least common multiple of a and b.
14        lcm_of_a_b = lcm(a, b)
15      
16        # Calculate an upper boundary for the search space (this is not tight).
17        r = (a + b) * n
18      
19        # Use binary search to find the nth magical number.
20        # The key function calculates the number of magical numbers 
21        # less than or equal to 'x' by summing the number of multiples of 'a' and 'b',
22        # then subtracting the number of multiples of 'lcm_of_a_b' to avoid double counting.
23        nth_magical = bisect_left(range(r), n, key=lambda x: x // a + x // b - x // lcm_of_a_b)
24      
25        # Return the nth magical number modulo MOD.
26        return nth_magical % MOD
27

1class Solution {
2    // Define modulus constant for the problem
3    private static final int MOD = (int) 1e9 + 7;
4
5    // Function to find the nth magical number
6    public int nthMagicalNumber(int n, int a, int b) {
7        // Calculate least common multiple of a and b using gcd (Greatest Common Divisor)
8        int leastCommonMultiple = a * b / gcd(a, b);
9      
10        // Initialize binary search bounds
11        long lowerBound = 0;
12        long upperBound = (long) (a + b) * n;
13
14        // Binary search to find the smallest number that is the nth magical number
15        while (lowerBound < upperBound) {
16            // Middle of the current bounds
17            long mid = (lowerBound + upperBound) >>> 1;
18
19            // Check if the mid number is a valid magical number by counting
20            // all multiples of a and b up to mid, minus those of their lcm to avoid double-counting
21            if (mid / a + mid / b - mid / leastCommonMultiple >= n) {
22                // If count is equal or greater than n, we shrink the right bound
23                upperBound = mid;
24            } else {
25                // Otherwise, we need to look for a larger number
26                lowerBound = mid + 1;
27            }
28        }
29
30        // After binary search, lower bound is our nth magical number
31        // Return it modulo MOD
32        return (int) (lowerBound % MOD);
33    }
34
35    // Utility method to calculate the greatest common divisor using Euclid's algorithm
36    private int gcd(int a, int b) {
37        // Recursive calculation of gcd
38        return b == 0 ? a : gcd(b, a % b);
39    }
40}
41

1#include <numeric> // Include necessary library for std::lcm
2
3class Solution {
4public:
5    const int MOD = 1e9 + 7; // Use uppercase for constants
6
7    int nthMagicalNumber(int n, int a, int b) {
8        int lcm_ab = std::lcm(a, b); // Calculate the least common multiple of a and b
9        long long left = 0, right = 1LL * (a + b) * n; // Use long long for large ranges
10      
11        // Perform a binary search to find the nth magical number
12        while (left < right) {
13            long long mid = (left + right) / 2; // Calculate the middle value
14            // Check if the mid value has n or more multiples of a or b, considering overlaps
15            if (mid / a + mid / b - mid / lcm_ab >= n)
16                right = mid; // Too high, decrease right
17            else
18                left = mid + 1; // Too low, increase left
19        }
20      
21        return left % MOD; // Return the nth magical number modulo MOD
22    }
23};
24

1function lcm(a: number, b: number): number {
2    // Calculate the greatest common divisor (GCD) using Euclid's algorithm
3    function gcd(a: number, b: number): number {
4        while (b !== 0) {
5            let t = b;
6            b = a % b;
7            a = t;
8        }
9        return a;
10    }
11
12    // Calculate the least common multiple (LCM) using the relationship between GCD and LCM
13    return (a * b) / gcd(a, b);
14}
15
16const MOD: number = 1e9 + 7; // Use uppercase for constants
17
18function nthMagicalNumber(n: number, a: number, b: number): number {
19    // Calculate the least common multiple of a and b
20    let lcmAB: number = lcm(a, b); 
21    let left: number = 0, right: number = (a + b) * n; // Use `number` type for the range
22  
23    // Perform a binary search to find the nth magical number
24    while (left < right) {
25        let mid: number = Math.floor((left + right) / 2); // Calculate the middle value
26
27        // Check if the mid value has n or more multiples of a or b, considering overlaps
28        if (Math.floor(mid / a) + Math.floor(mid / b) - Math.floor(mid / lcmAB) >= n)
29            right = mid; // Too high, adjust the right boundary
30        else
31            left = mid + 1; // Too low, adjust the left boundary
32    }
33  
34    // Return the nth magical number modulo MOD
35    return left % MOD; 
36}
37
38// Usage
39// let result = nthMagicalNumber(n, a, b); // Invoke the function with desired values of n, a, and b
40

Time and Space Complexity

Time Complexity

The given code snippet finds the nth magical number where a magical number is a number divisible by either a or b.

To analyze the time complexity, let's consider the operations performed:

Calculating the least common multiple (lcm) of a and b. The time complexity of finding the lcm depends on the algorithm used. If the Euclidean algorithm is used to find the gcd (greatest common divisor), then this part of the code has a time complexity of O(log(min(a, b)).
The bisect_left function performs a binary search. The parameter range(r) has a length of about Nx(a+b)/lcm(a,b). The binary search algorithm has a time complexity of O(log n), but since it's not searching through a simple list but using a lambda function to generate values on the fly, the key function is calculated for every middle element in each iteration of the binary search. This, therefore, results in a time complexity of O(log(Nx(a+b)/lcm(a,b)) * log(min(a, b))) because each key calculation is O(log(min(a, b))).
The modulo operation is constant time, O(1).

Given these points, the overall time complexity is O(log(Nx(a+b)/lcm(a,b)) * log(min(a, b))).

Space Complexity

The code uses a constant amount of extra space:

Storing variables such as mod, c, and r requires O(1) space.
The bisect_left function does not create additional data structures that scale with the input size, since the range does not actually create a list but is an iterator.

The lambda function within bisect_left is stateless and does not consume more memory proportional to the size of the input. Therefore, the overall space complexity of the provided function is O(1) (constant space).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know