Problem 878

Abstract / Summary

Find the nth smallest number divisible by either of two given numbers.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0878.py

class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        # reminds me of FizzBuzz

        # compute n for x
        def count(x):
            # actually the result can be wrong:
            # I don't check whether x is magical
            one  = x // a
            two  = x // b
            both = x // lcm(a, b) # it's possible that a and b share some factors
            return one + two - both

        left  = 0
        right = a * n # rough estimate
        while left < right:
            mid = (left + right) // 2
            if count(mid) < n:
                left  = mid + 1
            else:
                right = mid

        return left % 1_000_000_007
23 lines | 721 bytes | submitted November 27, 2023 | GitHub   37% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 37% (100k+ submissions).

Typical patterns to solve this problem:
  • Binary Search
  • Math
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation computes the n-th magical number-an integer that is divisible by either of the two given divisors a or b. It does so by combining a counting helper with a binary-search loop that narrows the search interval until the exact value is found. The final result is reduced modulo 1 000 000 007 as required by the problem statement.

Counting magical numbers up to a bound

A nested function named count determines how many magical numbers are less than or equal to a candidate value x. The function uses integer division to count multiples of each divisor and then subtracts the overlap counted twice.

def count(x):
    one  = x // a
    two  = x // b
    both = x // lcm(a, b)
    return one + two - both

The subtraction of both eliminates the double-counted numbers that are multiples of the least common multiple of a and b. By employing the lcm function, the code correctly handles the situation where a and b share common factors, ensuring that the overlap is computed precisely.

Initial search interval

Before the binary search begins, the algorithm establishes a lower bound of 0 and an upper bound based on a simple over-estimate: the product of a and n. This choice guarantees that the n-th magical number lies within the interval, even when a is the smaller divisor.

left  = 0
right = a * n

Binary-search loop

The core of the algorithm is a classic binary-search loop that repeatedly halves the interval. At each iteration, the midpoint mid is evaluated with the count helper. If fewer than n magical numbers exist up to mid, the lower bound moves just beyond mid; otherwise, the upper bound contracts to mid. The loop terminates when left meets right, at which point left holds the smallest value whose count is at least n.

while left < right:
    mid = (left + right) // 2
    if count(mid) < n:
        left  = mid + 1
    else:
        right = mid

Because the interval is reduced by roughly half each iteration, the loop converges quickly even for very large inputs.

Final modulo operation

After the binary search finishes, the algorithm returns the found magical number reduced modulo 1 000 000 007. Performing the modulo only once, after the search, avoids unnecessary arithmetic inside the loop and keeps the inner computation fast.

return left % 1_000_000_007

Edge-case handling

The code gracefully deals with inputs where a and b are not coprime. By using the least common multiple in the overlap calculation, it correctly counts numbers that are multiples of both divisors, preventing an inflated count. The initial upper bound a * n also covers the case where a is larger than b, ensuring that the search space always contains the target value regardless of the relative sizes of the divisors.

When n is very large, the binary-search approach still operates efficiently because the number of iterations depends logarithmically on the size of the interval rather than linearly on n. The use of integer division (//) guarantees that the counting operation remains exact and fast for all integer inputs.

Performance optimizations

The algorithm’s primary optimization is the binary-search strategy, which reduces the problem of locating the n-th magical number to a logarithmic number of checks. Each check consists of a few integer divisions and a subtraction, all of which are O(1) operations on typical hardware. By calculating the least common multiple once per count call, the code avoids repeated factorization or gcd calculations inside the loop.

Additionally, the modulo operation is deferred until after the search completes, preventing repeated large-integer modulo calculations that could degrade performance. The choice of right = a * n as the initial bound provides a tight enough interval to keep the number of binary-search steps modest while still guaranteeing correctness.

written by openai gpt

ELI5 - Simplified Explanation

Imagine there is a magical garden where some flowers only bloom on certain days. Some flowers bloom every time the number of days is a multiple of a first number, and others bloom when the number of days is a multiple of a second number. The goal is to find the specific day when a certain amount of these magical flowers have finished blooming.

To find the right day, the code starts by picking a range that might contain the answer. It looks at the middle of this range and asks how many magical flowers would have bloomed by that time. If the number of flowers is too small, it knows the day must be later, so it throws away the first half of the range. If there are enough flowers, it focuses on the earlier half to see if it can find an even sooner day. By repeating this process over and over, the range gets smaller and smaller until it finds the exact day needed. Because the final result might be a very large number, it uses a special trick to keep the number manageable by dividing it by a large round value and keeping the remainder.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.30 | σ = 1.54

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Go Python
LeetcodeHelp C++ Java Python
Progiez C++ Java Python
github black-shadows C++
charles-wangkai Java
everthis JS
fpdjsns C++
gouthampradhan Java
halfrost Go
JoshCrozier JS
ruoru Rust
suxrobGM C#
wisdompeak C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fpdjsns C++
gouthampradhan Java
halfrost Go
JoshCrozier JavaScript
ruoru Rust
suxrobGM C#
wisdompeak C++
zfang399 C++
28 links | 16 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

10 solutions   November 27, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality