Count The Triplets Problem

Count The Triplets

Problem Statement

Given an array A[] consisting of N integers. The task is to count the number of triples (A[i], A[j], A[k]), where i, j, and k denote the respective indices, such that one of the integers can be written as the summation of the other two integers.

Examples:

Input:  A[] = {1, 2, 3, 4, 5}
Output: 4
Explanation:
The valid triplets are –

  • (1, 2, 3) : 1 + 2 = 3
  • (2, 3, 5) : 2 + 3 = 5
  • (1, 3, 4) : 1 + 3 = 4
  • (1, 4, 5) : 1 + 4 = 5

Input: A[] = {2, 3, 6,9}
Output: 1


Basic Approach

The most basic approach is to run three nested loops from 1 till N and check if the summation of any two integers equals the third integer.

C++ Implementation

count_Triplets(int A[], int N){
     int count = 0;
     sort(A, A + N);
     for(int i = 0; i < N; i++){
       for(int j = i + 1; j < N; j++){
          for(int k = j + 1; k < N; k++){
              if(A[i] + A[j] == A[k]){
                    count++;
              }
          }
       }
     }
  return count; 
}

Java Implementation

count_Triplets(int[] A, int N){
     int count = 0;
     Arrays.sort(A);
     for(int i = 0; i < N; i++){
       for(int j = i + 1; j < N; j++){
          for(int k = j + 1; k < N; k++){
              if(A[i] + A[j] == A[k]){
                    count++;
              }
          }
       }
     }
  return count; 
}

Python Implementation

def count_Triplets(A, N):
     count = 0
     A.sort()
     for i in range(N):
         for j in range(i + 1, N):
             for k in range(j + 1, N):
                 if A[i] + A[j] == A[k]:
                      count = count + 1
 
     return count

Time Complexity: O(N^3) where N is the number of nodes of the binary tree.Space Complexity: O(1)


Efficient Approach (Using Hashing)

The approach is to calculate all possible combinations such that the summation of any two integers is equal to the third integers. If we observe carefully, there can only be 4 possible cases, which satisfy the above condition.

  • (0, 0, 0) : As 0 + 0 = 0, it is a valid triplet. Therefore, the total possible ways = freq[0]C3, as among all possible frequencies of 0, we just need to consider triplets.
  • (0, x, x) : As 0 + x = x, it is a valid triplet. Therefore, the total possible ways = freq[x]C2 * freq[0]C1, as among all possible frequencies of 0 and x, we just need to consider the triplet containing one 0 and two x.
  • (x, x, 2x) : As x + x = 2x, it is a valid triplet. Therefore, the total possible ways = freq[x]C2 * freq[2x]C1, as among all possible frequencies of x and 2x, we just need to consider the triplet containing one 2x and one x.
  • (x, y, x + y) : The total possible ways = freq[x]C1 * freq[y]C1 * freq[x + y]C1, as among all possible frequencies of x, y and x + y, we just need to consider the triplet containing all x, y and x + y.
Count the Triplets Image2

Algorithm

  • Compute the value of the maximum element, mx of the array.
  • Build a frequency array, freq of size mx + 1 and store the frequency of all the elements of the array A[].
  • Initialise a count variable and consider the above four cases one by one:
    • If the triplet is (0, 0, 0), add freq[0]C3 to count.
    • If the triplet is (0, x, x), add freq[0]C1 * freq[x]C2 to count.
    • If the triplet is (x, x, 2x), add freq[x]C2 * freq[2x]C1 to count.
    • If the triplet is (x, y, x + y), add freq[x]C1 * freq[y]C1 * freq[x + y]C1 to count.
  • Return count.

C++ Code For Hashing Method

int count_triplets(int A[], int N){
        int max_val = 0;
        for (int i = 0; i < n; i++)
            max_val = max(max_val, A[i]);
        int freq[max_val + 1]={0};
        for (int i = 0; i < n; i++)
            freq[A[i]]++;
 
        int count = 0;  
    
        count += freq[0] * (freq[0] - 1) * (freq[0] - 2) / 6;
 
        for (int i = 1; i <= max_val; i++){
            count += freq[0] * freq[i] * (freq[i] - 1) / 2;
        }
 
        for (int i = 1; 2 * i <= max_val; i++){
            count += freq[i] * (freq[i] - 1) / 2 * freq[2 * i];
        }
 
        for (int i = 1; i <= max_val; i++) {
            for (int j = i + 1; i + j <= max_val; j++)
                count += freq[i] * freq[j] * freq[i + j];
        }
 
        return count;
    }

Java Code For Hashing Method

count_Triplets(int[] A, int N){
        int max_val = 0;
        for (int i = 0; i < N; i++)
            max_val = Math.max(max_val, A[i]);
        int[] freq = new int[max_val + 1];
        for (int i = 0; i < N; i++)
            freq[A[i]]++;
 
        int count = 0; 
 
        count += freq[0] * (freq[0] - 1) * (freq[0] - 2) / 6;
 
        for (int i = 1; i <= max_val; i++)
            count += freq[0] * freq[i] * (freq[i] - 1) / 2;
 
   
        for (int i = 1; 2 * i <= max_val; i++)
            count += freq[i] * (freq[i] - 1) / 2 * freq[2 * i];
 
        for (int i = 1; i <= max_val; i++) {
            for (int j = i + 1; i + j <= max_val; j++)
                count += freq[i] * freq[j] * freq[i + j];
        }
 
        return count;
}

Python Code For Hashing Method

def count_Triplets(A, N):
    max_val = 0
    for i in range(n):
        max_val = max(max_val, A[i])
 
    freq = [0 for i in range(max_val + 1)]
 
    for i in range(n):
        freq[A[i]] += 1
 
    count = 0 
 
 
    count += (freq[0] * (freq[0] - 1) *
           (freq[0] - 2) // 6)
 
    for i in range(1, max_val + 1):
        count += (freq[0] * freq[i] *
               (freq[i] - 1) // 2)
 
    for i in range(1, (max_val + 1) // 2):
        count += (freq[i] *
               (freq[i] - 1) // 2 * freq[2 * i])
 
    for i in range(1, max_val + 1):
        for j in range(i + 1, max_val - i + 1):
            count += freq[i] * freq[j] * freq[i + j]
 
    return count

Time Complexity: O(N^2) where N is the number of nodes of the binary tree.
Space Complexity: O(N), as a map is used.


Practice Questions

Maximum Sum Triplets
3 Sum Zero


Frequently Asked Questions

How do you count triplets in an array?
The triplets can be counted by running three nested loops over the size of the array.

What are triplets in an array?
The triplet of an array is a tuple of three elements of different indices, represented by (i, j, k).

Previous Post
Median Of Two Sorted Arrays

Median of Two Sorted Arrays

Next Post
Bitbucket Vs GitHub

Bitbucket vs GitHub: Full Comparison

Crack your next tech interview with confidence!
Take a free mock interview, get instant⚡️ feedback and recommendation💡
Take Free Mock Interview
Total
0
Share