Partition the array into three equal sum segments | First segment 's end index ; Third segment 's start index ; This function returns true if the array can be divided into three equal sum segments ; Prefix Sum Array ; Suffix Sum Array ; Stores the total sum of the array ; We can also take pre [ pos2 - 1 ] - pre [ pos1 ] == total_sum / 3 here . ; Driver Code
< ? php $ pos1 = -1 ; $ pos2 = -1 ; function equiSumUtil ( $ arr ) { global $ pos2 , $ pos1 ; $ n = count ( $ arr ) ; $ pre = array_fill ( 0 , $ n , 0 ) ; $ sum = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ sum += $ arr [ $ i ] ; $ pre [ $ i ] = $ sum ; } $ suf = array_fill ( 0 , $ n , 0 ) ; $ sum = 0 ; for ( $ i = $ n - 1 ; $ i >= 0 ; $ i -- ) { $ sum += $ arr [ $ i ] ; $ suf [ $ i ] = $ sum ; } $ total_sum = $ sum ; $ i = 0 ; $ j = $ n - 1 ; while ( $ i < $ j - 1 ) { if ( $ pre [ $ i ] == $ total_sum / 3 ) { $ pos1 = $ i ; } if ( $ suf [ $ j ] == $ total_sum / 3 ) { $ pos2 = $ j ; } if ( $ pos1 != -1 && $ pos2 != -1 ) { if ( $ suf [ $ pos1 + 1 ] - $ suf [ $ pos2 ] == $ total_sum / 3 ) { return true ; } else { return false ; } } if ( $ pre [ $ i ] < $ suf [ $ j ] ) { $ i ++ ; } else { $ j -- ; } } return false ; } function equiSum ( $ arr ) { global $ pos2 , $ pos1 ; $ ans = equiSumUtil ( $ arr ) ; if ( $ ans ) { print ( " First ▁ Segment ▁ : ▁ " ) ; for ( $ i = 0 ; $ i <= $ pos1 ; $ i ++ ) { print ( $ arr [ $ i ] . " " ) ; } print ( " STRNEWLINE " ) ; print ( " Second ▁ Segment ▁ : ▁ " ) ; for ( $ i = $ pos1 + 1 ; $ i < $ pos2 ; $ i ++ ) { print ( $ arr [ $ i ] . " " ) ; } print ( " STRNEWLINE " ) ; print ( " Third ▁ Segment ▁ : ▁ " ) ; for ( $ i = $ pos2 ; $ i < count ( $ arr ) ; $ i ++ ) { print ( $ arr [ $ i ] . " " ) ; } print ( " STRNEWLINE " ) ; } else { println ( " Array ▁ cannot ▁ be ▁ divided ▁ into ▁ " , " three ▁ equal ▁ sum ▁ segments " ) ; } } $ arr = array ( 1 , 3 , 6 , 2 , 7 , 1 , 2 , 8 ) ; equiSum ( $ arr ) ; ? >