Online Judge Solutions

Saturday, December 6, 2014

LintCode: Kth Prime Number

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.
The eligible numbers are like 3, 5, 7, 9, 15 ...
Example
If k=4, return 9.

 
/*
class Solution {
public:
    long long kthPrimeNumber(int k) {
       
        vector<long long>  h(k+1, 0);
       
        h[0] = 1;
        int i3 = 0, i5 = 0, i7 = 0;
       
        for(int i = 1; i <= k; i++) {
            long long x3 = 3 * h[i3], x5 = 5*h[i5], x7 = 7 * h[i7];
            h[i] = min(x3, min(x5, x7));
           
            if (x3 == h[i]) i3++;
            if (x5 == h[i]) i5++;
            if (x7 == h[i]) i7++;
        }
       
        return h[k];
    }
};

class Solution {
public:
    long long kthPrimeNumber(int k) {
        queue<long long> q3, q5, q7;
       
        q3.push(3); q5.push(5); q7.push(7);
       
        long long result;
        for(int i = 0; i < k; i++) {
            long long t3 = q3.size() > 0? q3.front() : LONG_MAX;
            long long t5 = q5.size() > 0? q5.front() : LONG_MAX;
            long long t7 = q7.size() > 0? q7.front() : LONG_MAX;
           
            result = min(t3, min(t5, t7));
            if (result == t3) {
                q3.pop();
                q3.push(result*3);
                q5.push(result*5);
            }
            if (result == t5){
                q5.pop();
                q5.push(result*5);
            }
            if (result == t7)
                q7.pop();
           
            q7.push(result*7);
        }
        return result;
    }
};
*/
class Solution {
public:
    long long kthPrimeNumber(int k) {
       
        vector<long long>  h(k+1, 0);
       
        h[0] = 1;
        int i3 = 0, i5 = 0, i7 = 0;
       
        for(int i = 1; i <= k; i++) {
            long long x3 = 3 * h[i3], x5 = 5*h[i5], x7 = 7 * h[i7];
            h[i] = min(x3, min(x5, x7));
           
            while(h[i3]*3 <= h[i]) i3++;
            while(h[i5]*5 <= h[i]) i5++;
            while(h[i7]*7 <= h[i]) i7++;
        }
       
        return h[k];
    }
};

No comments:

Post a Comment