Binary Search in C, 8ms


  • 0
    W
    int nth(long long n) {
        if (n > INT_MAX) return INT_MAX;
        
        int ans = 0;
        
        int k0 = 1 + (int)log2(n);
        int a0 = pow(2, k0-1);
        
        for (long long t1=1; t1<=n; t1*=5) {
            while (a0 * t1 > n) {
                k0--;
                a0 = a0 >> 1;
            }
            int k = k0;
            int a = a0;
            for (long long t2=t1; t2<=n; t2*=3) {
                while (a * t2 > n) {
                    k--;
                    a = a>>1;
                }
                ans += k;
            }
        }
        return ans;
    }
    
    int nthUglyNumber(int n) {
        long long b = 0;
        long long e = 1;
        while (nth(e) < n) {
            b = e;
            e *= 2;
        }
        if (e > INT_MAX) e = INT_MAX;
        
        while (b <= e) {
            long long m = (b + e) / 2;
            (nth(m) < n) ? (b=m+1) : (e=m-1);
        }
        return b;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.