Partition the array into three equal sum segments | 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
def equiSumUtil ( arr , pos1 , pos2 ) : NEW_LINE INDENT n = len ( arr ) ; NEW_LINE pre = [ 0 ] * n ; NEW_LINE sum = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += arr [ i ] ; NEW_LINE pre [ i ] = sum ; NEW_LINE DEDENT suf = [ 0 ] * n ; NEW_LINE sum = 0 ; NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT sum += arr [ i ] ; NEW_LINE suf [ i ] = sum ; NEW_LINE DEDENT total_sum = sum ; NEW_LINE i = 0 ; NEW_LINE j = n - 1 ; NEW_LINE while ( i < j - 1 ) : NEW_LINE INDENT if ( pre [ i ] == total_sum // 3 ) : NEW_LINE INDENT pos1 = i ; NEW_LINE DEDENT if ( suf [ j ] == total_sum // 3 ) : NEW_LINE INDENT pos2 = j ; NEW_LINE DEDENT if ( pos1 != - 1 and pos2 != - 1 ) : NEW_LINE INDENT if ( suf [ pos1 + 1 ] - suf [ pos2 ] == total_sum // 3 ) : NEW_LINE INDENT return [ True , pos1 , pos2 ] ; NEW_LINE DEDENT else : NEW_LINE INDENT return [ False , pos1 , pos2 ] ; NEW_LINE DEDENT DEDENT if ( pre [ i ] < suf [ j ] ) : NEW_LINE INDENT i += 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT j -= 1 ; NEW_LINE DEDENT DEDENT return [ False , pos1 , pos2 ] ; NEW_LINE DEDENT def equiSum ( arr ) : NEW_LINE INDENT pos1 = - 1 ; NEW_LINE pos2 = - 1 ; NEW_LINE ans = equiSumUtil ( arr , pos1 , pos2 ) ; NEW_LINE pos1 = ans [ 1 ] ; NEW_LINE pos2 = ans [ 2 ] ; NEW_LINE if ( ans [ 0 ] ) : NEW_LINE INDENT print ( " First ▁ Segment ▁ : ▁ " , end = " " ) ; NEW_LINE for i in range ( pos1 + 1 ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT print ( " " ) ; NEW_LINE print ( " Second ▁ Segment ▁ : ▁ " , end = " " ) ; NEW_LINE for i in range ( pos1 + 1 , pos2 ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT print ( " " ) ; NEW_LINE print ( " Third ▁ Segment ▁ : ▁ " , end = " " ) ; NEW_LINE for i in range ( pos2 , len ( arr ) ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT print ( " " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT println ( " Array ▁ cannot ▁ be ▁ divided ▁ into " , " three ▁ equal ▁ sum ▁ segments " ) ; NEW_LINE DEDENT DEDENT arr = [ 1 , 3 , 6 , 2 , 7 , 1 , 2 , 8 ] ; NEW_LINE equiSum ( arr ) ; NEW_LINE