Discussion on: Daily Challenge #199 - List of All Rationals

[Vidit Sarkar]

C++

// returns the pos-th element in the allRationals list as a pair
// like allRationals(0) = [1,1], allRationals(10) = [5,2]
pair<int, int> allRationals(int pos){
    queue<pair<int,int>> rationals; // for storing like BFS
    rationals.push(make_pair(1,1)); // push the first pair
    int index = 0; // index of element in BFS array

    while(true){
        pair<int, int> p = rationals.front();
        if(index++ == pos)
            return p;
        rationals.pop();
        rationals.push(make_pair(p.first, p.first+p.second)); // push the left child [a,a+b]
        rationals.push(make_pair(p.first+p.second,p.second)); // push the right child [a+b,b]
    }
}

// if the rationals-list is required upto index pos, then this function can be used
// same as allRationals, but we are also storing elements in the vector
// Example: rationals(4) = [[1,1], [1,2], [2,1], [1,3], [3,2]]
vector<pair<int,int>> rationals(int pos){
    queue<pair<int,int>> rationals; // for storing like BFS
    rationals.push(make_pair(1,1)); // push the first pair
    vector<pair<int,int> > rationalsArray;
    int index = 0; // index of element in BFS array

    while(true){
        pair<int, int> p = rationals.front();
        rationalsArray.push_back(p);
        if(index++ == pos)
            return rationalsArray;
        rationals.pop();
        rationals.push(make_pair(p.first, p.first+p.second)); // push the left child [a,a+b]
        rationals.push(make_pair(p.first+p.second,p.second)); // push the right child [a+b,b]
    }
}