Skip to content

Latest commit

 

History

History
140 lines (99 loc) · 3.35 KB

0878._Nth_Magical_Number.md

File metadata and controls

140 lines (99 loc) · 3.35 KB

878. Nth Magical Number

难度: Hard

刷题内容

原题连接

内容描述

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

Return the N-th magical number.  Since the answer may be very large, return it modulo 10^9 + 7.

 

Example 1:

Input: N = 1, A = 2, B = 3
Output: 2
Example 2:

Input: N = 4, A = 2, B = 3
Output: 6
Example 3:

Input: N = 5, A = 2, B = 4
Output: 10
Example 4:

Input: N = 3, A = 6, B = 4
Output: 8
 

Note:

1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

解题方案

思路 1 - 时间复杂度: O(A+B)- 空间复杂度: O(1)******

数学题直接看的solution：

  • 从数据范围看来，N高达10^9，直接遍历不现实
  • 注意到魔法数是有循环的，我们令P=A和B的最小公倍数，那么在每P个数中，魔法数的数量和位置都是相同的，因此我们只需要计算[1,p]中间的魔法数
  • [1,p]的魔法数数量是 P/A+P/B-1，注意到，P是A和B的最小公倍数，因此[1,p]中，既能被A整除，也能被B整除，只有一个数，就是P
  • 现在问题变成，在[1,p]中，求第n个魔法数

注意到，我们在[1,p]中任取一个数x（x<p），[1,x]中魔法数的数量是x/A+x/B，注意这个是整除。

class Solution(object):
    def nthMagicalNumber(self, N, A, B):
        """
        :type N: int
        :type A: int
        :type B: int
        :rtype: int
        """
        def gcd(a, b):
            if b == 0:
                return a
            return gcd(b, a % b)
        
        def lcm(a, b):
            return a * b // gcd(a, b)
        
        MOD = 10**9 + 7

        L = lcm(A, B)
        M = L // A + L // B - 1
        q, r = divmod(N, M)

        if r == 0:
            return q * L % MOD

        heads = [A, B]
        for _ in range(r - 1):
            if heads[0] <= heads[1]:
                heads[0] += A
            else:
                heads[1] += B

        return (q * L + min(heads)) % MOD

思路 2 - 时间复杂度: O(log(Nmax(A,B)))- 空间复杂度: O(1)*****

从另外一个角度来看，如果我们知道了一个数字x，那么我们可以轻易算出有多少个magic number 是小于等于x的， 即x // A + x // B - x // L, 其中L = lcm(A, B), 我们可以通过二分法算出一个最小的数字num，小于等于num的magic number 数量刚好是N, 然后这个num就是我们要求的 Nth Magical Number

时间复杂度为O(log(N∗max(A,B))), beats 100%

class Solution(object):
    def nthMagicalNumber(self, N, A, B):
        """
        :type N: int
        :type A: int
        :type B: int
        :rtype: int
        """
        def gcd(a, b):
            if b == 0:
                return a
            return gcd(b, a % b)
        
        def lcm(a, b):
            return a * b // gcd(a, b)
        
        MOD = 10**9 + 7
        L = lcm(A, B)

        def magic_below_x(x):
            # How many magical numbers are <= x?
            return x // A + x // B - x // L

        l, r = 0, N * max(A,B)
        while l <= r:
            mid = l + ((r-l) >> 1)
            if magic_below_x(mid) < N:
                l = mid + 1
            else:
                r = mid - 1

        return l % MOD