Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 878 with 18 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 878 # by problem number
lcpy gen -s nth_magical_number # by problem name
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 10^9 + 7.
Input: n = 1, a = 2, b = 3
Output: 2
Input: n = 4, a = 2, b = 3
Output: 6
O(log(n * min(a, b))) time complexity?
from math import gcd
class Solution:
# Time: O(log(n * min(a, b)))
# Space: O(1)
def nth_magical_number(self, n: int, a: int, b: int) -> int:
mod = 10**9 + 7
lcm = a * b // gcd(a, b)
def count(x: int) -> int:
return x // a + x // b - x // lcm
low, high = 1, n * min(a, b)
while low < high:
mid = (low + high) // 2
if count(mid) >= n:
high = mid
else:
low = mid + 1
return low % mod
| Time | Space |
|---|---|
| O(log(n * min(a, b))) | O(1) |