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

: 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`(0, 0, 0)`

**${freq[0] \choose 3}$**.: 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`(0, x, x)`

**${freq[x] \choose 2}$*****${freq[0] \choose 1}$**.: 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`(x, x, 2x)`

**${freq[x] \choose 2}$*****${freq[2x] \choose 1}$**.: The total number of ways is given by the formula`(x, y, x + y)`

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