K-th Smallest Prime Fraction Solutions in C++

/// Source : https://leetcode.com/problems/k-th-smallest-prime-fraction/description/
/// Author : liuyubobobo
/// Time   : 2018-03-10

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Binary Search
/// Time Complexity: O(len(A)^2*logW)
/// Space Complexity: O(1)
class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {

        sort(A.begin(), A.end());
        double l = 0.0, r = 1.0;
        while(l <= r){
            double mid = (l + r) / 2.0;
            vector<int> res = under(A, mid);
            // cout << mid << " " << res[0] << " " << res[1] << " " << res[2] << endl;
            if(res[0] == K)
                return {res[1], res[2]};

            if(res[0] < K)
                l = mid;
            else
                r = mid;
        }

        assert(false);
        return {};
    }

private:
    // return {count, num, denom}
    vector<int> under(const vector<int>& A, double x){
        int res = 0;
        double max_frac = 0.0;
        int num, denom;
        for(int i = 0 ; i < A.size() ; i ++)
            for(int j = i + 1 ; j < A.size() ; j ++){
                double frac = (double)A[i] / A[j];
                if(frac <= x){
                    res ++;
                    if(frac > max_frac){
                        max_frac = frac;
                        num = A[i];
                        denom = A[j];
                    }
                }
            }

        return {res, num, denom};
    }
};

void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> A1 = {1, 2, 3, 5};
    print_vec(Solution().kthSmallestPrimeFraction(A1, 3));

    vector<int> A2 = {1, 7};
    print_vec(Solution().kthSmallestPrimeFraction(A2, 1));

    return 0;
}

/// Source : https://leetcode.com/problems/k-th-smallest-prime-fraction/description/
/// Author : liuyubobobo
/// Time   : 2018-03-10

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Binary Search
/// A little bit optimization from previous solution
///
/// Time Complexity: O(len(A)^2*logW)
/// Space Complexity: O(1)
class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {

        sort(A.begin(), A.end());
        double l = 0.0, r = 1.0;
        while(l <= r){
            double mid = (l + r) / 2.0;
            vector<int> res = under(A, mid);
            // cout << mid << " " << res[0] << " " << res[1] << " " << res[2] << endl;
            if(res[0] == K)
                return {res[1], res[2]};

            if(res[0] < K)
                l = mid;
            else
                r = mid;
        }

        assert(false);
        return {};
    }

private:
    // return {count, num, denom}
    vector<int> under(const vector<int>& A, double x){
        int res = 0;
        double max_frac = 0.0;
        int num, denom;
        for(int j = 1 ; j < A.size() ; j ++)
            for(int i = 0 ; i < j ; i ++){
                double frac = (double)A[i] / A[j];
                if(frac < x){
                    res ++;
                    if(frac > max_frac){
                        max_frac = frac;
                        num = A[i];
                        denom = A[j];
                    }
                }
                else
                    break;
            }

        return {res, num, denom};
    }
};

void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> A1 = {1, 2, 3, 5};
    print_vec(Solution().kthSmallestPrimeFraction(A1, 3));

    vector<int> A2 = {1, 7};
    print_vec(Solution().kthSmallestPrimeFraction(A2, 1));

    return 0;
}

/// Source : https://leetcode.com/problems/k-th-smallest-prime-fraction/description/
/// Author : liuyubobobo
/// Time   : 2018-03-10

#include <iostream>
#include <vector>
#include <cassert>
#include <queue>

using namespace std;

/// Heap
/// Time Complexity: O(len(A)^2*log(len(A)^2))
/// Space Complexity: O(len(A)^2)
class Solution {

private:
    class ComparePair{
    public:
        bool operator()(const pair<int, int>& p1,
                        const pair<int, int>& p2){
            return p1.first * p2.second < p2.first * p1.second;
        }
    };

public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {

        sort(A.begin(), A.end());

        priority_queue<pair<int, int>,
                       vector<pair<int, int>>,
                       ComparePair> pq;
        for(int i = 0 ; i < A.size() ; i ++)
            for(int j = i + 1 ; j < A.size() ; j ++)
                if(pq.size() != K)
                    pq.push(make_pair(A[i], A[j]));
                else if(A[i] * pq.top().second < pq.top().first * A[j]){
                    pq.pop();
                    pq.push(make_pair(A[i], A[j]));
                }

        return {pq.top().first, pq.top().second};
    }
};

void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> A1 = {1, 2, 3, 5};
    print_vec(Solution().kthSmallestPrimeFraction(A1, 3));

    vector<int> A2 = {1, 7};
    print_vec(Solution().kthSmallestPrimeFraction(A2, 1));

    return 0;
}

/// Source : https://leetcode.com/problems/k-th-smallest-prime-fraction/description/
/// Author : liuyubobobo
/// Time   : 2018-03-10

#include <iostream>
#include <vector>
#include <cassert>
#include <queue>

using namespace std;

/// Heap
/// Optimization from previous solution
///
/// Time Complexity: O(len(A)^2*log(len(A)^2))
/// Space Complexity: O(len(A)^2)
class Solution {

public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {

        sort(A.begin(), A.end());

        auto cmp = [&A](const pair<int, int>& p1, const pair<int, int>& p2){
            return A[p1.first] * A[p2.second] > A[p2.first] * A[p1.second];
        };
        priority_queue<pair<int, int>,
                vector<pair<int, int>>,
                decltype(cmp)> pq(cmp);
        for(int i = 1 ; i < A.size() ; i ++)
            pq.push(make_pair(0, i));

        for(int i = 0 ; i < K - 1 ; i ++){
            pair<int, int> cur_smallest = pq.top();
            pq.pop();
            cur_smallest.first ++;
            if(cur_smallest.first < cur_smallest.second)
                pq.push(cur_smallest);
        }

        return {A[pq.top().first], A[pq.top().second]};
    }
};

void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> A1 = {1, 2, 3, 5};
    print_vec(Solution().kthSmallestPrimeFraction(A1, 3));

    vector<int> A2 = {1, 7};
    print_vec(Solution().kthSmallestPrimeFraction(A2, 1));

    return 0;
}