two standard dp solutions


  • 17
    S
    // three lists:
    // (1) 1×2, 2×2, 3×2, 4×2, 5×2, …
    // (2) 1×3, 2×3, 3×3, 4×3, 5×3, …
    // (3) 1×5, 2×5, 3×5, 4×5, 5×5, …
    
    // O(n) time, O(n) space 
    int nthUglyNumber(int n) {
        vector<int> d(n, 0);
        d[0] = 1;
        
        int f2 = 2, f3 = 3, f5 = 5;     // min values for multipy factor 2, 3, 5
        int ix2 = 0, ix3 = 0, ix5 = 0;  // indexs for min values of f2, f3, f5 
        
        for (int i = 1; i < n; ++i) {
            int minV = min(min(f2, f3), f5);
            d[i] = minV;
            
            if (minV == f2) f2 = 2 * d[++ix2];
            if (minV == f3) f3 = 3 * d[++ix3];
            if (minV == f5) f5 = 5 * d[++ix5];
        }
        
        return d[n-1];
    }
    
    // O(n) (might be more) time, O(3n) space
    int nthUglyNumber1(int n) {
        queue<int> q1, q2, q3;
        q1.push(1), q2.push(1), q3.push(1);
        
        int m = 0;
        for (int i = 0; i < n; ++i) {
            m = min(min(q1.front(), q2.front()), q3.front());
            if (m == q1.front()) q1.pop();
            if (m == q2.front()) q2.pop();
            if (m == q3.front()) q3.pop();
            q1.push(2*m);
            q2.push(3*m);
            q3.push(5*m);
        }
        
        return m;
    }

Log in to reply
 

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