Leetcode 878 Nth Magical Number

发表于 |

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. 1 <= N <= 10^9
  2. 2 <= A <= 40000
  3. 2 <= B <= 40000
    2，3，4，6，8，9，10，12，14，15，16

分析:

  1. 在极大的范围内找到一个数,使其满足某种条件，显然是二分法
  2. 对于找到的某个数K，要判断其是不是正好是满足条件的第N个数，也就是判断是不是刚好有N-1个满足条件的数比他小。
  3. 举个例子，N，A，B = 11，2，3
    1. 我们用二分搜索搜到了16，那么比16小的2的倍数的数有2，4，6，8，10，12，14，共7个
    2. 比16小的3的倍数的数有3，6，9，12，15共5个
    3. 其中6，12重复了，故应减去这两个数，而这也正好是A,B最小公倍数即6的倍数
    4. 故比16小且满足条件的数共有7+5-2=10，说明16正好是第11个数

思路：

  1. 先找到A,B的最小公倍数
  2. 二分计算结果
  3. mod 1e9+7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution(object):
    def nthMagicalNumber(self, N, A, B):
        """
        :type N: int
        :type A: int
        :type B: int
        :rtype: int
        """
        mod = 10**9 + 7
        A,B = min(A,B),max(A,B)
        def gcd(a,b):
            if not b: return a
            return gcd(b,a%b)
        def lcm(a,b):
            if a*b == 0: return 0
            return int(a*b/gcd(a,b))
        C = lcm(A,B)
        
        lo = 1
        hi = 10**14
        while lo < hi:
            mid = (lo+hi) / 2
            num1 = int(math.ceil(mid/float(A))) - 1
            num2 = int(math.ceil(mid/float(B))) - 1
            num3 = int(math.ceil(mid/float(C))) - 1
            
            if num1+num2-num3 == N-1  and (mid % A == 0 or mid % B == 0): return mid % mod
            
            elif num1+num2-num3 > N-1:
                hi = mid
            
            else:
                lo = mid+1

66 / 66 test cases passed.
difficulty: hard
Runtime: 24 ms