Count possible removals to make absolute difference between the sum of odd and even indexed elements equal to K | C ++ program for the above approach ; Function to check if difference between the sum of odd and even indexed elements after removing the first element is K or not ; Stores the sum of elements at odd and even indices ; Return 1 if difference is K ; Function to check if difference between the sum of odd and even indexed elements after removing the second element is K or not ; Stores the sum of elements at odd and even indices ; Return 1 if difference is K ; Function to count number of elements to be removed to make sum of differences between odd and even indexed elements equal to K ; Size of given array ; Base Conditions ; Stores prefix and suffix sums ; Base assignments ; Store prefix sums of even indexed elements ; Store prefix sums of odd indexed elements ; Similarly , store suffix sums of elements at even and odd indices ; Stores the count of possible removals ; Traverse and remove the ith element ; If the current element is excluded , then previous index ( i - 1 ) points to ( i + 2 ) and ( i - 2 ) points to ( i + 1 ) ; Find count when 0 th element is removed ; Find count when 1 st element is removed ; Count gives the required answer ; Driver Code ; Function call
#include " bits / stdc + + . h " NEW_LINE using namespace std ; int findCount0th ( vector < int > & arr , int N , int K ) { int oddsum = 0 , evensum = 0 ; for ( int i = 1 ; i < N ; i += 2 ) { oddsum += arr [ i ] ; } for ( int i = 2 ; i < N ; i += 2 ) { evensum += arr [ i ] ; } if ( abs ( oddsum - evensum ) == K ) return 1 ; else return 0 ; } int findCount1st ( vector < int > & arr , int N , int K ) { int evensum = arr [ 0 ] , oddsum = 0 ; for ( int i = 3 ; i < N ; i += 2 ) { evensum += arr [ i ] ; } for ( int i = 2 ; i < N ; i += 2 ) { oddsum += arr [ i ] ; } if ( abs ( oddsum - evensum ) == K ) return 1 ; else return 0 ; } int countTimes ( vector < int > & arr , int K ) { int N = ( int ) arr . size ( ) ; if ( N == 1 ) return 1 ; if ( N < 3 ) return 0 ; if ( N == 3 ) { int cnt = 0 ; cnt += ( abs ( arr [ 0 ] - arr [ 1 ] ) == K ? 1 : 0 ) + ( abs ( arr [ 2 ] - arr [ 1 ] ) == K ? 1 : 0 ) + ( abs ( arr [ 0 ] - arr [ 2 ] ) == K ? 1 : 0 ) ; return cnt ; } vector < int > prefix ( N + 2 , 0 ) ; vector < int > suffix ( N + 2 , 0 ) ; prefix [ 0 ] = arr [ 0 ] ; prefix [ 1 ] = arr [ 1 ] ; suffix [ N - 1 ] = arr [ N - 1 ] ; suffix [ N - 2 ] = arr [ N - 2 ] ; for ( int i = 2 ; i < N ; i += 2 ) { prefix [ i ] = arr [ i ] + prefix [ i - 2 ] ; } for ( int i = 3 ; i < N ; i += 2 ) { prefix [ i ] = arr [ i ] + prefix [ i - 2 ] ; } for ( int i = N - 3 ; i >= 0 ; i -= 2 ) { suffix [ i ] = arr [ i ] + suffix [ i + 2 ] ; } for ( int i = N - 4 ; i >= 0 ; i -= 2 ) { suffix [ i ] = arr [ i ] + suffix [ i + 2 ] ; } int count = 0 ; for ( int i = 2 ; i < N ; i ++ ) { if ( abs ( prefix [ i - 1 ] + suffix [ i + 2 ] - prefix [ i - 2 ] - suffix [ i + 1 ] ) == K ) { count ++ ; } } count += findCount0th ( arr , N , K ) ; count += findCount1st ( arr , N , K ) ; return count ; } int main ( ) { vector < int > arr = { 1 , 2 , 4 , 5 , 6 } ; int K = 2 ; cout << countTimes ( arr , K ) ; return 0 ; }