Count ways to split array into two equal sum subarrays by changing sign of any one array element | C ++ program for the above approach ; Function to count ways of splitting the array in two subarrays of equal sum by changing sign of any 1 element ; Stores the count of elements in prefix and suffix of array ; Stores the total sum of array ; Traverse the array ; Increase the frequency of current element in suffix ; Stores prefix sum upto an index ; Stores sum of suffix from an index ; Stores the count of ways to split the array in 2 subarrays having equal sum ; Traverse the array ; Modify prefix sum ; Add arr [ i ] to prefix Map ; Calculate suffix sum by subtracting prefix sum from total sum of elements ; Remove arr [ i ] from suffix Map ; Store the difference between the subarrays ; Check if diff is even or not ; Count number of ways to split array at index i such that subarray sums are same ; Update the count ; Return the count ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSubArraySignChange ( int arr [ ] , int N ) { unordered_map < int , int > prefixCount ; unordered_map < int , int > suffixCount ; int total = 0 ; for ( int i = N - 1 ; i >= 0 ; i -- ) { total += arr [ i ] ; suffixCount [ arr [ i ] ] ++ ; } int prefixSum = 0 ; int suffixSum = 0 ; int count = 0 ; for ( int i = 0 ; i < N - 1 ; i ++ ) { prefixSum += arr [ i ] ; prefixCount [ arr [ i ] ] ++ ; suffixSum = total - prefixSum ; suffixCount [ arr [ i ] ] -- ; int diff = prefixSum - suffixSum ; if ( diff % 2 == 0 ) { int x = prefixCount + suffixCount [ - diff / 2 ] ; count = count + x ; } } return count ; } int main ( ) { int arr [ ] = { 2 , 2 , -3 , 3 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countSubArraySignChange ( arr , N ) ; return 0 ; }