1201. Ugly Number III

An ugly number is a positive integer that is divisible by ab, or c.

Given four integers nab, and c, return the nth ugly number.

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

Example 4:

Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984

Constraints:

  • 1 <= n, a, b, c <= 10^9
  • 1 <= a * b * c <= 10^18
  • It is guaranteed that the result will be in range [1, 2 * 10^9].

这道题是丑陋数系列的第三道题,前两道分别是 Ugly Number IIUgly Number。这里可能有的童鞋会说这不就是把第二道中的 2,3,和5换成了这里的 a,b,和c么,就想着直接套用前一道的方法来做。然而这道题的丑陋数和之前两道的定义却不太相同,之前两道定义的丑陋数是只有质数因子 2,3,5 的数字,而这里定义的是可以被 a,b,和c整除的数字,就更为宽泛了,只要能被 a,b,和c中的任意一个或多个整除的数字都是丑陋数,不管还能不能被其他别的数字整除。对于 [1, num] 范围内的整数,能被a整除的数字的个数为 num/a,而能被a或b整除的数字却不是 num/a + num/b,因为会存在同时被a和b整除的数字,若a和b是两个质数,比如2和3,那么就是 num/a + num/b - num/ab,但a和b不一定互质的两个数字,可能含有共同的非1因子,所以更为严谨的写法就是 num/a + num/b - num/lcm(a,b),这里的 lcm 指的是最小公倍数 Least Common Multiple,小学数学里应该都学过。同理,对于 [1, num] 范围内的整数,能被a,b,或c整除的数字的个数为 num/a + num/b + num/c - num/lcm(a,b) - num/lcm(b,c) - num/lcm(a,c) + num/lcm(a,b,c),同时脑海中可以出现那个经典的三圆相交的图形,论坛上的帖子也有这个图形。

这里的最小公倍数用代码怎么求呢,还是通过小学数学知识,两个数字的最小公倍数等于二者之积除以最大公约数 Greatest Common Divisor。而求 gcd 在之前的题目中就用过了,比如 Max Points on a Line,甚至还有求字符串 gcd 的题目 Greatest Common Divisor of Strings。既然能有一个公式可以快速的计算出某个范围内丑陋数的总个数,而且题目也给了所求结果的范围 [1, 2 * 10^9],用二分搜索法简直是再合适不过了,这是博主之前的总结帖 LeetCode Binary Search Summary 二分搜索法小结 中的第四类。确定了 left 和 right 的初始范围之后,就可以折中求出 mid 了,然后代入上面的公式求出 [1, mid] 范围内共有 cnt 个丑陋数字,并用 cnt 和给定的n进行比较,若 cnt 小于n,则 left 更新为 mid+1,反之,right 更新为 mid,最终返回 right 即可,参见代码如下:

class Solution {
public:
    int nthUglyNumber(int n, int a, int b, int c) {
        int left = 0, right = 2e9;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int cnt = mid / a + mid / b + mid / c - mid / lcm(a, b) - mid / lcm(b, c) - mid / lcm(a, c) + mid / lcm(a, lcm(b, c));
            if (cnt < n) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
    long gcd(long a, long b) {
        return a == 0 ? b : gcd(b % a, a);
    }
    long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1201

类似题目:

Ugly Number II

Ugly Number

Super Ugly Number

Max Points on a Line

参考资料:

https://leetcode.com/problems/ugly-number-iii/

https://leetcode.com/problems/ugly-number-iii/discuss/387539/cpp-Binary-Search-with-picture-and-Binary-Search-Template

https://leetcode.com/problems/ugly-number-iii/discuss/387780/JavaC%2B%2B-Binary-Search-with-Venn-Diagram-Explain-Math-Formula

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation