Scale Engineer

Nth Magical Number

Hard
#0832Time: O(n * min(a, b)) - The n-th magical number can be as large as `n * min(a, b)`. The loop runs up to this value, making it prohibitively slow for large `n`.Space: O(1) - Constant space is used as we only need a few variables to store the current number and the count.
Patterns
Math
Algorithms
Binary Search

Prompt

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

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 1, a = 2, b = 3
Output: 2

Example 2:

Input: n = 4, a = 2, b = 3
Output: 6

 

Constraints:

  • 1 <= n <= 109
  • 2 <= a, b <= 4 * 104

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most straightforward and naive approach. We can simply iterate through all positive integers, starting from 1. For each integer, we check if it's a magical number (i.e., divisible by a or b). We use a counter to keep track of how many magical numbers we have found. When the counter reaches n, the current integer is our answer.

Algorithm

  • Initialize a counter count to 0 and a number num to 1.
  • Start an infinite loop.
  • In each iteration, check if num is divisible by a or b.
  • If it is, increment count.
  • If count becomes equal to n, it means num is the n-th magical number. Return num % (10^9 + 7).
  • If count is not yet n, increment num and continue to the next iteration.

Walkthrough

The algorithm works by simulating the process of finding magical numbers one by one. It starts checking from num = 1. In a loop, it tests the condition num % a == 0 || num % b == 0. If this condition is true, we've found a magical number, so we increment a counter. We repeat this process, incrementing num each time, until our counter reaches the target n. The value of num at that point is the n-th magical number. While simple, its performance is directly tied to the magnitude of the final answer, which can be very large.

class Solution {    public int nthMagicalNumber(int n, int a, int b) {        long MOD = 1_000_000_007;        long num = 1;        int count = 0;         while (count < n) {            if (num % a == 0 || num % b == 0) {                count++;            }            if (count == n) {                return (int)(num % MOD);            }            num++;        }         return -1; // Should not be reached    }}

Complexity

Time

O(n * min(a, b)) - The n-th magical number can be as large as `n * min(a, b)`. The loop runs up to this value, making it prohibitively slow for large `n`.

Space

O(1) - Constant space is used as we only need a few variables to store the current number and the count.

Trade-offs

Pros

  • Very simple to understand and implement.

  • Requires minimal mathematical insight.

Cons

  • Extremely inefficient for large values of n.

  • Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.

Solutions

class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int nthMagicalNumber ( int n , int a , int b ) { int c = a * b / gcd ( a , b ); long l = 0 , r = ( long ) ( a + b ) * n ; while ( l < r ) { long mid = l + r >>> 1 ; if ( mid / a + mid / b - mid / c >= n ) { r = mid ; } else { l = mid + 1 ; } } return ( int ) ( l % MOD ); } private int gcd ( int a , int b ) { return b == 0 ? a : gcd ( b , a % b ); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem