1201. Ugly Number III

Link

Solution

我們觀察到當mid使得條件 (mid以下的ugliy number 數 >= n)成立時， mid+1 也會使條件也會成立，有以上這種單調性就可以用binary search。

這題的概念類似前幾個題目，都是找到一個最小值使得條件成立。

public int nthUglyNumber(int n, int a, int b, int c) {
    int min = Math.min(Math.min(a,b), c);
    int max = 2000000000;

    while(max > min){
        int mid = min + (max-min)/2;
        if(isEnough(mid, n)){
            max = mid;
        }else{
            min = mid+1;
        }
    }
    return (int)min;
}


public boolean isEnough(int cur, int n){
    int total;
    //do something
    return total >= n;
}

卡的點是要怎麼計算total?

看解答後，聰明的方法如下:

  long ab = lcm((long)a,(long)b); //a,b 最小公倍數       
  long bc = lcm((long)b, (long)c);//b,c 最小公倍數  
  long ac = lcm((long)a,(long)c);//a,c 最小公倍數  
        
  long abc = lcm(ab, (long)c); //a,b,c 最小公倍數  
  
  long total = cur/a + cur/b + cur/c - cur/ab - cur/bc - cur/ac + (cur/abc);

然後就是怎麼求出lcm

 public long gcd(long a, long b) {
        if (b==0) return a;
        return gcd(b,a%b);
}
    
public long lcm(long a, long b){
    return (long)(a*b/gcd(a,b));
}

最後答案:

    public int nthUglyNumber(int n, int a, int b, int c) {
        int min = Math.min(Math.min(a,b), c);
        int max = 2000000000;
        long ab = lcm((long)a,(long)b);
        
        long bc = lcm((long)b, (long)c);

        long ac = lcm((long)a,(long)c);
        
        long abc = lcm(ab, (long)c);
        
        while(max > min){
            int mid = min + (max-min)/2;
            if(isEnough(mid, a, b, c, ab, ac, bc, abc, n)){
                max = mid;
            }else{
                min = mid+1;
            }
        }
        return (int)min;
    }
    
    public long gcd(long a, long b) {
        if (b==0) return a;
        return gcd(b,a%b);
    }
    
    public long lcm(long a, long b){
        return (long)(a*b/gcd(a,b));
    }
    
    public boolean isEnough(int cur, int a, int b, int c, long ab, long ac, long bc, long abc, int n){
        long total = cur/a + cur/b + cur/c - cur/ab - cur/bc - cur/ac + (cur/abc);
        return total >= n;
    }