## 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)**:**(0, x, x)**:**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**.

**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- 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**.

- If the triplet is
- 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).**