Find Partition Line such that sum of values on left and right is equal | Python3 implementation of the approach ; Function that returns true if the required line exists ; To handle negative values from x [ ] ; Update arr [ ] such that arr [ i ] contains the sum of all v [ j ] such that x [ j ] = i for all valid values of j ; Update arr [ i ] such that arr [ i ] contains the sum of the subarray arr [ 0. . . i ] from the original array ; If all the points add to 0 then the line can be drawn anywhere ; If the line is drawn touching the leftmost possible points ; If the line is drawn just before the current point ; If the line is drawn touching the current point ; If the line is drawn just after the current point ; If the line is drawn touching the rightmost possible points ; Driver code
MAX = 1000 ; NEW_LINE def lineExists ( x , y , v , n ) : NEW_LINE INDENT size = ( 2 * MAX ) + 1 ; NEW_LINE arr = [ 0 ] * size ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT arr [ x [ i ] + MAX ] += v [ i ] ; NEW_LINE DEDENT for i in range ( 1 , size ) : NEW_LINE INDENT arr [ i ] += arr [ i - 1 ] ; NEW_LINE DEDENT if ( arr [ size - 1 ] == 0 ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT if ( arr [ size - 1 ] - arr [ 0 ] == 0 ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT for i in range ( 1 , size - 1 ) : NEW_LINE INDENT if ( arr [ i - 1 ] == arr [ size - 1 ] - arr [ i - 1 ] ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT if ( arr [ i - 1 ] == arr [ size - 1 ] - arr [ i ] ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT if ( arr [ i ] == arr [ size - 1 ] - arr [ i ] ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT DEDENT if ( arr [ size - 2 ] == 0 ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT return False ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT x = [ - 3 , 5 , 8 ] ; NEW_LINE y = [ 8 , 7 , 9 ] ; NEW_LINE v = [ 8 , 2 , 10 ] ; NEW_LINE n = len ( x ) ; NEW_LINE if ( lineExists ( x , y , v , n ) ) : NEW_LINE INDENT print ( " Yes " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) ; NEW_LINE DEDENT DEDENT