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. Triple sum
  2. Discussions

Triple sum

Sort by

recency

|

221 Discussions

|

  • adimurti911
     + 0 comments

    def triplets(a, b, c): a.sort() c.sort() count = 0 for b_val in b: count_a = sum(1 for x in a if x <= b_val) count_c = sum(1 for y in c if b_val>=y) count += count_a * count_c return count

    Why is this partially correct?

  • torexed
     + 0 comments

    Used set to remove duplicates and create order. Put data back into vectors to retrieve indices for upper bound checks.

    // Complete the triplets function below.
long triplets(vector<int> a, vector<int> b, vector<int> c) {
    long result = 0;
    std::set<int> setA{a.begin(), a.end()};
    std::set<int> setB{b.begin(), b.end()};
    std::set<int> setC{c.begin(), c.end()};
    
    std::vector<int> orderedA {setA.begin(), setA.end()};
    std::vector<int> orderedC {setC.begin(), setC.end()};
    
    for (const auto& itemB : setB)
    {
        auto idxA = std::upper_bound(orderedA.begin(), orderedA.end(), itemB);
        auto idxC = std::upper_bound(orderedC.begin(), orderedC.end(), itemB);
        auto aDiff = idxA - orderedA.begin();
        auto cDiff = idxC - orderedC.begin();
        result += aDiff * cDiff;
    }
    
    return result;
}

  • cherrymeteor
     + 0 comments

    javascript

    function triplets(a, b, c) {
  let cleanA = [...new Set(a)].sort((a, b) => a - b)
  let cleanB = [...new Set(b)].sort((a, b) => a - b)
  let cleanC = [...new Set(c)].sort((a, b) => a - b)

  let count = 0
  for (let i = 0; i < cleanB.length; i++) {
    let howManyA = cleanA.findIndex(v => v > cleanB[i])
    let howManyC = cleanC.findIndex(v => v > cleanB[i])
    if (howManyA == -1) howManyA = cleanA.length
    if (howManyC == -1) howManyC = cleanC.length
    
    count += howManyA * howManyC
  }
  return count
}

  • urossevkusic
     + 0 comments

    My algorithm works as follows:: 1. remove duplicates from all vectors (generate sets, then recreate vectors); note that the vectors are now sorted because std::set is an ordered collection 2. for all elements q in B, find the number of elements r in C such that q <= r using binary search, and store the results in vector. Also, generate a prefix sum of that vector starting from its end. 3. for all elements p in A, find the first element q in B such that p <= q. Simply add all triplets with q' >= q in B, that are now stored in the prefix sum array of B.

    long long triplets(vector<int> a, vector<int> b, vector<int> c) {
    std::set<int> ta(a.begin(), a.end());
    std::set<int> tb(b.begin(), b.end());
    std::set<int> tc(c.begin(), c.end());
    std::vector<long long> A(ta.begin(), ta.end()), B(tb.begin(), tb.end()), C(tc.begin(), tc.end());
    long long count = 0;
    std::vector<long long> pref(B.size());
    pref[B.size() - 1] = std::distance(C.begin(), std::upper_bound(C.begin(), C.end(), B[B.size() - 1]));
    for(int i = B.size() - 2; i >= 0; --i) {
        auto it = std::upper_bound(C.begin(), C.end(), B[i]);
        pref[i] = pref[i + 1] + std::distance(C.begin(), it);
    }
    
    for(int p : A) {
        auto it = std::lower_bound(B.begin(), B.end(), p);
        if(it == B.end()) continue;
        else count += pref[std::distance(B.begin(), it)];
    }
    return count;
}

  • cherrymeteor
     + 0 comments

    JS all pass

    function triplets(a, b, c) {
  let cleanA = [...new Set(a)].sort((x, y) => x - y)
  let cleanB = [...new Set(b)]
  let cleanC = [...new Set(c)].sort((x, y) => x - y)
  let count = 0

  for (let i = 0; i < cleanB.length; i++) {
    let numOfP = 0, numOfQ = 0
    for (let j = cleanA.length; j > 0; j--) {
      if (cleanA[j - 1] <= cleanB[i]) {
        numOfP = j
        break
      }
    }
    for (let j = cleanC.length; j > 0; j--) {
      if (cleanC[j - 1] <= cleanB[i]) {
        numOfQ = j
        break
      }
    }
    count += numOfP * numOfQ
  }
  return count
}