leetcode 1201. Ugly Number III

Seawolf

1. Write a program to find the n-th ugly number.
   
2. 
   
3. Ugly numbers are positive integers which are divisible by a or b or c.
   
4. 
   
5. 
   
6. 
   
7. Example 1:
   
8. 
   
9. Input: n = 3, a = 2, b = 3, c = 5
   
10. Output: 4
    
11. Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.
    
12. Example 2:
    
13. 
    
14. Input: n = 4, a = 2, b = 3, c = 4
    
15. Output: 6
    
16. Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.
    
17. Example 3:
    
18. 
    
19. Input: n = 5, a = 2, b = 11, c = 13
    
20. Output: 10
    
21. Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.
    
22. Example 4:
    
23. 
    
24. Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
    
25. Output: 1999999984
    
26. 
    
27. 
    
28. Constraints:
    
29. 
    
30. 1 <= n, a, b, c <= 10^9
    
31. 1 <= a * b * c <= 10^18
    
32. It's guaranteed that the result will be in range [1, 2 * 10^9]

复制代码

1. class Solution {
   
2.     public static int nthUglyNumber(int n, int a, int b, int c) {
   
3.         int start = 1,end = Integer.MAX_VALUE,mid;
   
4.         
   
5.         while(start < end){
   
6.             mid = start + (end - start) / 2;
   
7.             if(count(a,b,c,mid) < n) start = mid + 1;
   
8.             else {
   
9.                 end = mid;
   
10.             }
    
11.         }
    
12.         
    
13.         return end;
    
14.     }
    
15.     static long stein(long a, long b){
    
16.         int acc = 0;
    
17.     while ((a & 1) == 0 && (b & 1) == 0) {
    
18.         acc++;
    
19.         a >>= 1;
    
20.         b >>= 1;
    
21.     }
    
22.     while ((a & 1) == 0) a >>= 1;
    
23.     while ((b & 1) == 0) b >>= 1;
    
24.     if (a < b) { long t = a; a = b; b = t; }
    
25.     while ((a = (a - b) >> 1) != 0) {
    
26.         while ((a & 1) == 0) a >>= 1;
    
27.         if (a < b) { long t = a; a = b; b = t; }
    
28.     }
    
29.     return b << acc;
    
30. 
    
31.         
    
32.     }
    
33.    
    
34.     static long lcm(long a, long b){
    
35.         
    
36.         return a*b / stein(a,b);
    
37.     }
    
38.    
    
39.     static long count (long a, long b, long c, long num){
    
40.         
    
41.         return ((num / a) + (num / b) + (num / c)
    
42.                 - (num / lcm(a, b))
    
43.                 - (num / lcm(b, c))
    
44.                 - (num / lcm(a, c))
    
45.                 + (num / lcm(a, lcm(b, c))));
    
46.     }  
    
47. }

复制代码