We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Beautiful Quadruples
  5. Discussions

Beautiful Quadruples

  • ihorfinance
     + 2 comments

    C++(more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star:) )

    1. count by B pairs where A<=B (array length should be C, init with zeros) - sum of this array is a total count of quadruples
    2. accumulate above count for each B
    3. count by B how times unique xor's happaned for pairs AB (so we have a frequency matrix, where row is B and column is xor)
    4. acummulate above matrix by row (by B)
    5. iterate over all pairs CD where C<D and look at above matrix for C^D and subtract the found count from total count at step 1. This difference will be the final result.


    Main points:

    1. constrain that we use only pairs where x<=y filters pairs so count of x and y is unique (if we had 12, no need for 21)
    2. use accumulation containers to not recompute frequencies again and again
    3. x^y = 0 when x == y, in our case when A^B == C ^ D
    size_t beautifulQuadruples(
    int const _num1, 
    int const _num2, 
    int const _num3, 
    int const _num4
){
    using namespace  std;
    using vec = vector<size_t>;
    auto nums{vector<int>{_num1, _num2, _num3, _num4}};
    sort(begin(nums), end(nums));
    auto pairNum1Num2Counts{vec(nums.at(2) + 1, 0)};
    iota(begin(pairNum1Num2Counts), begin(pairNum1Num2Counts) + nums.at(0), 0);
    fill(begin(pairNum1Num2Counts) + nums.at(0), begin(pairNum1Num2Counts) +
        nums.at(1) + 1, nums.at(0));
    partial_sum(begin(pairNum1Num2Counts), end(pairNum1Num2Counts),
        begin(pairNum1Num2Counts));
    auto xorNum2Counts{vector<vec>(nums.at(2) + 1,
        vec(static_cast<size_t>(pow(2, ceil(log2f(nums.at(3) + 1)))) + 1, 0))};
    for(auto num1{1}; num1 <= nums.at(0); ++num1){
        for(auto num2{num1}; num2 <= nums.at(1); ++num2){
            ++xorNum2Counts.at(num2).at(num1 ^ num2);
        }
    }
    transform(begin(xorNum2Counts) + 1, end(xorNum2Counts), begin(xorNum2Counts),
        begin(xorNum2Counts) + 1, [&](auto & xorCountsThis, auto & xorCountsPrev){
            transform(begin(xorCountsThis), end(xorCountsThis), begin(xorCountsPrev),
                begin(xorCountsThis), [&](auto xorCountThis, auto xorCountPrev){
                    return xorCountThis + xorCountPrev;
                });
                return xorCountsThis;
        });
    size_t pairsXorZeroCount = 0;
    for(auto num3{1}; num3 <= nums.at(2); ++num3){
        for(auto num4{num3}; num4 <= nums.at(3); ++num4){
            pairsXorZeroCount += pairNum1Num2Counts.at(num3) -
                xorNum2Counts.at(num3).at(num3 ^ num4);
        }
    }
    return pairsXorZeroCount;
}