Count Triplets such that one of the numbers can be written as sum of the other two | Python3 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
import math as mt NEW_LINE def countWays ( arr , n ) : NEW_LINE INDENT max_val = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT max_val = max ( max_val , arr [ i ] ) NEW_LINE DEDENT freq = [ 0 for i in range ( max_val + 1 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT freq [ arr [ i ] ] += 1 NEW_LINE DEDENT ans += ( freq [ 0 ] * ( freq [ 0 ] - 1 ) * ( freq [ 0 ] - 2 ) // 6 ) NEW_LINE for i in range ( 1 , max_val + 1 ) : NEW_LINE INDENT ans += ( freq [ 0 ] * freq [ i ] * ( freq [ i ] - 1 ) // 2 ) NEW_LINE DEDENT for i in range ( 1 , ( max_val + 1 ) // 2 ) : NEW_LINE INDENT ans += ( freq [ i ] * ( freq [ i ] - 1 ) // 2 * freq [ 2 * i ] ) NEW_LINE DEDENT for i in range ( 1 , max_val + 1 ) : NEW_LINE INDENT for j in range ( i + 1 , max_val - i + 1 ) : NEW_LINE INDENT ans += freq [ i ] * freq [ j ] * freq [ i + j ] NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE print ( countWays ( arr , n ) ) NEW_LINE