Count Triplets such that one of the numbers can be written as sum of the other two | C ++ program to count Triplets such that at least one of the numbers can be written as sum of the other two ; Function to count the number of ways to choose the triples ; compute the max value in the array and create frequency array of size max_val + 1. We can also use HashMap to store frequencies . We have used an array to keep remaining code simple . ; Case 1 : 0 , 0 , 0 ; Case 2 : 0 , x , x ; Case 3 : x , x , 2 * x ; Case 4 : x , y , x + y iterate through all pairs ( x , y ) ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countWays ( int arr [ ] , int n ) { int max_val = 0 ; for ( int i = 0 ; i < n ; i ++ ) max_val = max ( max_val , arr [ i ] ) ; int freq [ max_val + 1 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) freq [ arr [ i ] ] ++ ; ans += freq [ 0 ] * ( freq [ 0 ] - 1 ) * ( freq [ 0 ] - 2 ) / 6 ; for ( int i = 1 ; i <= max_val ; i ++ ) ans += freq [ 0 ] * freq [ i ] * ( freq [ i ] - 1 ) / 2 ; for ( int i = 1 ; 2 * i <= max_val ; i ++ ) ans += 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 ++ ) ans += freq [ i ] * freq [ j ] * freq [ i + j ] ; } return ans ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << ( countWays ( arr , n ) ) ; return 0 ; }