Count Triplets

Problem Statement

An array of integers with the length n is presented to us as Arr[]. The objective is to determine the quantity of triplets (Arr[i],Arr[j],Arr[k]) such that any two numbers added together equal the third number.

Example

a, b, and c are members of Arr[] with indexes i, j, and k, respectively, such that 0<=i<j<k<n . Three for loops will be used to do this. If $x!=y!=z$ and $arr[x]+arr[y]=arr[z]$, increase the count. Let’s use examples to clarify.

Input

arr[]= { 1, 2, 2, 3, 4 }, N = 5

Output

Number of triplets: 4

Explanation

• Arr{} = [ 1, 2, 2, 3, 4 ] =(1, 2, 3) → 1 + 2 = 3
• Arr{} = [ 1, 2, 2, 3, 4 ] =(1, 2, 3) → 1 + 2 = 3
• Arr{} = [ 1, 2, 2, 3, 4 ] =(1, 3, 4) → 1 + 3 = 4
• Arr{} = [ 1, 2, 2, 3, 4 ] =(2, 2, 4) → 2 + 2 = 4

Input/Output

• Input
  An array is given as input and its size.
• Output
  Output is a single integer denoting the number of triplets in the array.

Constraints

• $3 <= \text{N} <= 100$
• $0 <= \text{arr[i]} <= 1000$

Approach1: Simple Approach

Algorithm

• We start with an integer array named Arr[] that has been filled with random numbers.
• The length of Arr is stored in variable N.
• Function count_Triplets(int arr[],int n) takes an array, its length returns the triplets in which one of the numbers can be written as sum of the other two
• Consider that the number of triplets’ initial variable count is 0.
• For each element of the triplet, traverse the array using three for loops.
• Outermost loop is $0<=i<n-2$, innermost loop is $i<j<n-1$ , and innermost loop is j<k<n.
• To see if $arr[i]+arr[j]==arr[k], arr[i]+arr[k]==arr[j]$, or $arr[k]+arr[j]==arr[i]$, check the equation. If true, increase the count.
• At the conclusion of all loops, count will contain the total number of triplets that satisfy the requirement.
• The result should be the count.

CPP Implementation:

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

int main() {
    // Your code goes here;
    int A[] = {5,7,12,3,2};
    int N = 5;
    cout << count_Triplets(A, N);
    return 0;
}

Java Implementation

import java.util.Arrays;   
class Main {
    static int count_Triplets(int[] A, int N){
     int count = 0;
     Arrays.sort(A);
     for(int i = 0; i < N; i++){  // for first number
       for(int j = i + 1; j < N; j++){  // for second number
          for(int k = j + 1; k < N; k++){  // for third number
              if(A[i] + A[j] == A[k]){
                    count++; // increment count
              }
          }
       }
     }
     return count; 
   }

    public static void main(String args[]) {
        // Your code goes here
        int[] A = { 5 ,7 ,12 ,3 ,2 };
        int N = 5;
        System.out.print(count_Triplets(A, N));
    }
}

Python Implementation:

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

     return count

A = [ 5,7,12,3,2 ]
N = 5
print(count_Triplets(A, N))

Output:

3

• Time Complexity: $O(N^3)$ where N is the size of the array.
  Since we are using three loops to iterate the array.
• Space Complexity: $O(1)$

Approach2: Efficient Approach (Using Hashing)

In this method, all combinations that result in any two integers added together equaling third integer , is calculated. If we pay close attention, we can see that there are only 4 scenarios that could meet the aforementioned requirement.

• (0, 0, 0): This triplet is legal since 0 + 0 = 0. Since we only need to take triplets into consideration among all potential frequencies of 0, the total number of ways is therefore equal to ${freq[0] \choose 3}$.
• (0, x, x): This triplet is valid since 0 + x = x. Since we only need to take into account the triplet having one 0 and two x among all possible frequencies of 0 and x, the total number of ways is therefore equal to ${freq[x] \choose 2}$ * ${freq[0] \choose 1}$.
• (x, x, 2x): This triplet is legal since x + x equals 2x. Because we only need to take into account the triplet containing one 2x and one x among all potential frequencies of x and 2x, the total number of ways is therefore equal to ${freq[x] \choose 2}$ * ${freq[2x] \choose 1}$.
• (x, y, x + y): The total number of ways is given by the formula ${freq[x] \choose 1}$ * ${freq[y] \choose 1}$ * ${freq[x+y] \choose 1}$, where we only need to take into account the triplet that contains all possible frequencies of x, y, and x + y.

where,
freq[x] = number of times x is present,
C-> Combination $(nCr= n!/((n-r)!*r!) )$

Algorithm

• Find the value of the array’s maximum element, mx.
• Create a frequency array named freq with the size mx + 1 and store the frequencies of each element of the array A[].
• Create a count variable, then take each of the four following scenarios into account:
• Add ${freq[0] \choose 3}$ to count if the triplet is (0, 0, 0).
• Add ${freq[x] \choose 2}$ * ${freq[0] \choose 1}$ to count if the triplet is (0, x, x).
• Add ${freq[x] \choose 2}$ * ${freq[2x] \choose 1}$ to count if the triplet is (x, x, 2x).
• If the triplet is (x, y, x + y), multiply the count by ${freq[x] \choose 1}$ * ${freq[y] \choose 1}$ * ${freq[x+y] \choose 1}$.
• Return count.

C++ Implementation:

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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]); //find max value
        int freq[max_val + 1]={0}; // create freq. array
        for (int i = 0; i < n; i++)
            freq[A[i]]++; 

        int count = 0;  
    // add all cases to count
        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; // count stores the answer
    }


int main() {
    // Your code goes here;
    int A[] = { 5 ,7 ,12 ,3 ,2 };
    int N = 5;
    cout << count_Triplets(A, N);
    return 0;
}

Java Implementation:

import java.util.Arrays;   
class Main {
    static int 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]); // find max value
        int[] freq = new int[max_val + 1]; // create freq array
        for (int i = 0; i < N; i++)
            freq[A[i]]++; // store value in freq array

        int count = 0; 
 // add all cases to count variable
        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; // count stores the answer
    }


    public static void main(String args[]) {
        // Your code goes here
        int[] A = { 5 ,7 ,12 ,3 ,2 };
        int N = 5;
        System.out.print(count_Triplets(A, N));
    }
}

Python Implementation:

def count_Triplets(A, n):
    max_val = 0
    for i in range(n):
        max_val = max(max_val, A[i]) #find_max_value

    freq = [0 for i in range(max_val + 1)]

    for i in range(n):
        freq[A[i]] += 1  # initialise_freq_array

    count = 0 

    # add all cases to count

    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 # count stores the answer


A = [ 5 ,7 ,12 ,3 ,2 ]
N = 5
print(count_Triplets(A, N))

Output:

3

Time Complexity: $O(N^2)$ where N is the number of nodes of the binary tree.
We are using two loops.

Space Complexity: $O(N)$, as a map is used.
Since we are using frequency array to store values.

Conclusion

• The triplet of an array is a tuple of three elements with various indices, denoted by (i, j, k).
• Given an array of unique numbers, the challenge is to find all the triplets where the total of the first two items equals the third.
• Three nested loops can be executed across the array’s length to count the triplets.
• Hash maps can be used to count the triplets.