Triple sum - Hacker Rank Solution

Given  arrays  of different sizes, find the number of distinct triplets  where  is an element of , written as , , and , satisfying the criteria: .

For example, given  and , we find four distinct triplets: .

Function Description

Complete the triplets function in the editor below. It must return the number of distinct triplets that can be formed from the given arrays.

triplets has the following parameter(s):

• a, b, c: three arrays of integers .

Input Format

The first line contains  integers , the sizes of the three arrays.
The next  lines contain space-separated integers numbering  respectively.

Constraints

Output Format

Print an integer representing the number of distinct triplets.

Sample Input 0

3 2 3
1 3 5
2 3
1 2 3

Sample Output 0

8 

Explanation 0

The special triplets are  .

Sample Input 1

3 3 3
1 4 5
2 3 3
1 2 3

Sample Output 1

5 

Explanation 1

The special triplets are 

Sample Input 2

4 3 4
1 3 5 7
5 7 9
7 9 11 13

Sample Output 2

12

Explanation 2

The special triplets are .

Triple sum - Hacker Rank Solution

First of all remove all duplicate elements from all  arrays(since, we need unique triplets).

The brute-force solution will be to count smaller than or equal to elements in array  and  linearly for every value in array and add the multiplication of their count in the  variable. This will take  complexity.

To solve it efficiently, first sort them in increasing order.

Now, for each element of array b, let say x, find the count of element smaller than or equal x in array a and c using binary-search and add the product of their counts in the final answer which is initialized as .

Let say  and  are two sets smaller than or equal to . So total number of their combinations possible is the cartesian product of these two sets i.e,

The required triplets are:

So, we have to multiply their counts to get the answer.

Problem Setter's code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int p,q,r,i,x,y;
    cin>>p>>q>>r;

    int a[p],b[q],c[r];
    for(i=0;i<p;++i) {
        cin>>a[i];
    }
    for(i=0;i<q;++i) {
        cin>>b[i];
    }
    for(i=0;i<r;++i) {
        cin>>c[i];
    }
    sort(a,a+p);
    sort(b,b+q);
    sort(c,c+r);

    long distinct_a[p],distinct_b[q],distinct_c[r];
    set<int> s;
    for(i=0;i<p;++i) {
        s.insert(a[i]);
        distinct_a[i]=s.size();
    }
    s.clear();
    for(i=0;i<q;++i) {
        s.insert(b[i]);
        distinct_b[i]=s.size();
    }
    s.clear();
    for(i=0;i<r;++i) {
        s.insert(c[i]);
        distinct_c[i]=s.size();
    }

    long ans=0;

    x = upper_bound(a,a+p,b[0])-a;
    y = upper_bound(c,c+r,b[0])-c;

    x-=1,y-=1;
    if(x>=0 && y>=0) {
        ans += distinct_a[x]*distinct_c[y];
    }

    for(i=1;i<q;++i) {
        if(b[i]!=b[i-1]) {
            x = upper_bound(a,a+p,b[i])-a;
            y = upper_bound(c,c+r,b[i])-c;

            x-=1,y-=1;
            if(x>=0 && y>=0) {
                ans += distinct_a[x]*distinct_c[y];
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}