Number of triangles possible with given lengths of sticks which are powers of 2 | Function to return the number of positive area triangles ; To store the count of total triangles ; To store the count of pairs of sticks with equal lengths ; Back - traverse and count the number of triangles ; Count the number of pairs ; If we have one remaining stick and we have a pair ; Count 1 triangle ; Reduce one pair ; Count the remaining triangles that can be formed ; Driver code
def countTriangles ( a , n ) : NEW_LINE INDENT cnt = 0 NEW_LINE pairs = 0 NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT pairs += a [ i ] // 2 NEW_LINE if ( a [ i ] % 2 == 1 and pairs > 0 ) : NEW_LINE INDENT cnt += 1 NEW_LINE pairs -= 1 NEW_LINE DEDENT DEDENT cnt += ( 2 * pairs ) // 3 NEW_LINE return cnt NEW_LINE DEDENT a = [ 1 , 2 , 2 , 2 , 2 ] NEW_LINE n = len ( a ) NEW_LINE print ( countTriangles ( a , n ) ) NEW_LINE