Count ways to split array into two equal sum subarrays by replacing each array element to 0 once | C ++ program for the above approach ; Function to find number of ways to split array into 2 subarrays having equal sum by changing element to 0 once ; Stores the count of elements in prefix and suffix of array elements ; Stores the sum of array ; Traverse the array ; Increase the frequency of current element in suffix ; Stores prefix sum upto index i ; Stores sum of suffix of index i ; Stores the desired result ; 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 ; Count number of ways to split the array at index i such that subarray sums are equal ; Update the final result ; Return the result ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSubArrayRemove ( int arr [ ] , int N ) { unordered_map < int , int > prefix_element_count , suffix_element_count ; int total_sum_of_elements = 0 ; for ( int i = N - 1 ; i >= 0 ; i -- ) { total_sum_of_elements += arr [ i ] ; suffix_element_count [ arr [ i ] ] ++ ; } int prefix_sum = 0 ; int suffix_sum = 0 ; int count_subarray_equal_sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { prefix_sum += arr [ i ] ; prefix_element_count [ arr [ i ] ] ++ ; suffix_sum = total_sum_of_elements - prefix_sum ; suffix_element_count [ arr [ i ] ] -- ; int difference = prefix_sum - suffix_sum ; int number_of_subarray_at_i_split = prefix_element_count [ difference ] + suffix_element_count [ - difference ] ; count_subarray_equal_sum += number_of_subarray_at_i_split ; } return count_subarray_equal_sum ; } int main ( ) { int arr [ ] = { 1 , 2 , 1 , 1 , 3 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countSubArrayRemove ( arr , N ) ; return 0 ; }