Number of triangles possible with given lengths of sticks which are powers of 2 | Java implementation of the approach ; 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
class GFG { static int countTriangles ( int a [ ] , int n ) { int cnt = 0 ; int pairs = 0 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { pairs += a [ i ] / 2 ; if ( a [ i ] % 2 == 1 && pairs > 0 ) { cnt += 1 ; pairs -= 1 ; } } cnt += ( 2 * pairs ) / 3 ; return cnt ; } public static void main ( String [ ] args ) { int a [ ] = { 1 , 2 , 2 , 2 , 2 } ; int n = a . length ; System . out . println ( countTriangles ( a , n ) ) ; } }