Find Partition Line such that sum of values on left and right is equal | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1000 ; bool lineExists ( int x [ ] , int y [ ] , int v [ ] , int n ) { int size = ( 2 * MAX ) + 1 ; long arr [ size ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { arr [ x [ i ] + MAX ] += v [ i ] ; } for ( int i = 1 ; i < size ; i ++ ) arr [ i ] += arr [ i - 1 ] ; if ( arr [ size - 1 ] == 0 ) return true ; if ( arr [ size - 1 ] - arr [ 0 ] == 0 ) return true ; for ( int i = 1 ; i < size - 1 ; i ++ ) { if ( arr [ i - 1 ] == arr [ size - 1 ] - arr [ i - 1 ] ) return true ; if ( arr [ i - 1 ] == arr [ size - 1 ] - arr [ i ] ) return true ; if ( arr [ i ] == arr [ size - 1 ] - arr [ i ] ) return true ; } if ( arr [ size - 2 ] == 0 ) return true ; return false ; } int main ( ) { int x [ ] = { -3 , 5 , 8 } ; int y [ ] = { 8 , 7 , 9 } ; int v [ ] = { 8 , 2 , 10 } ; int n = sizeof ( x ) / sizeof ( int ) ; if ( lineExists ( x , y , v , n ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }