LeetCode 878. Nth Magic Number - WoW
官方的题解在leetcode官网上, 想到lcm第一种解法还是比较容易的, 但是第二种binary search的方法并没有想到, 主要是没有想到对于每个数都先计算小于等于其的magic number个数有几个.
简介
题目给了两个数A和B, 然后定义magic number为要么能被A整除, 要么能被B整除的数, 然后要求第N个magic number. 就这么简单。
解法一. 算LCM, 然后剩下的一小部分挨个判断
假设两个数的最小公倍数$L = LCM(A, B)$, 那么对于[1, L]这个区间里的数, 能被A整除的有$\lfloor \frac{L}{A} \rfloor$, 能被B整数的有$\lfloor \frac{L}{B} \rfloor$, 这两部分除了L之外不会有重合的, 因为L是最小公倍数, 因此在$[1, L]$这个区间内有$M = \lfloor \frac{L}{A} \rfloor + \lfloor \frac{L}{B} \rfloor - 1$。
而$[L + 1, 2L]$这段区间中的magic number数目和第一段区间是一样的, 所以至少有$\lfloor \frac{min(A, B)}{L} \rfloor$个 magic number。但是最后还有一小段余数, 这一段直接暴力一个一个判断就好了, 反正最多不超过L个。
代码如下, gcd可以用辗转相除法得到, 然后$lcm = \frac{A \times B}{gcd(A, B)}$
Read full article from LeetCode 878. Nth Magic Number - WoW
No comments:
Post a Comment