Count Inversions of size three in a given array | Returns count of inversions of size 3 ; Initialize result ; Count all smaller elements on right of arr [ i ] ; Count all greater elements on left of arr [ i ] ; Update inversion count by adding all inversions that have arr [ i ] as middle of three elements ; Driver Code
< ? php function getInvCount ( $ arr , $ n ) { $ invcount = 0 ; for ( $ i = 1 ; $ i < $ n - 1 ; $ i ++ ) { $ small = 0 ; for ( $ j = $ i + 1 ; $ j < $ n ; $ j ++ ) if ( $ arr [ $ i ] > $ arr [ $ j ] ) $ small ++ ; $ great = 0 ; for ( $ j = $ i - 1 ; $ j >= 0 ; $ j -- ) if ( $ arr [ $ i ] < $ arr [ $ j ] ) $ great ++ ; $ invcount += $ great * $ small ; } return $ invcount ; } $ arr = array ( 8 , 4 , 2 , 1 ) ; $ n = sizeof ( $ arr ) ; echo " Inversion ▁ Count ▁ : ▁ " , getInvCount ( $ arr , $ n ) ; ? >