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
< ? php Function countTriangles ( $ a , $ n ) { $ cnt = 0 ; $ pairs = 0 ; for ( $ i = $ n - 1 ; $ i >= 0 ; $ i -- ) { $ pairs += $ a [ $ i ] / 2 ; if ( $ a [ $ i ] % 2 == 1 && $ pairs > 0 ) { $ cnt += 1 ; $ pairs -= 1 ; } } $ cnt += ( int ) ( ( 2 * $ pairs ) / 3 ) ; return $ cnt ; } $ a = array ( 1 , 2 , 2 , 2 , 2 ) ; $ n = sizeof ( $ a ) ; echo ( countTriangles ( $ a , $ n ) ) ; ? >