Partitioning into two contiguous element subarrays with equal sums | CPP Program to find the minimum element to be added such that the array can be partitioned into two contiguous subarrays with equal sums ; Structure to store the minimum element and its position ; initialize prefix and suffix sum arrays with 0 ; add current element to Sum ; add current element to Sum ; initialize the minimum element to be a large value ; check for the minimum absolute difference between current prefix sum and the next suffix sum element ; if prefixsum has a greater value then position is the next element , else it 's the same element. ; return the data in struct . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct data { int element ; int position ; } ; struct data findMinElement ( int arr [ ] , int n ) { struct data result ; int prefixSum [ n ] = { 0 } ; int suffixSum [ n ] = { 0 } ; prefixSum [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { prefixSum [ i ] = prefixSum [ i - 1 ] + arr [ i ] ; } suffixSum [ n - 1 ] = arr [ n - 1 ] ; for ( int i = n - 2 ; i >= 0 ; i -- ) { suffixSum [ i ] = suffixSum [ i + 1 ] + arr [ i ] ; } int min = suffixSum [ 0 ] ; int pos ; for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( abs ( suffixSum [ i + 1 ] - prefixSum [ i ] ) < min ) { min = abs ( suffixSum [ i + 1 ] - prefixSum [ i ] ) ; if ( suffixSum [ i + 1 ] < prefixSum [ i ] ) pos = i + 1 ; else pos = i ; } } result . element = min ; result . position = pos ; return result ; } int main ( ) { int arr [ ] = { 10 , 1 , 2 , 3 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; struct data values ; values = findMinElement ( arr , n ) ; cout << " Minimum ▁ element ▁ : ▁ " << values . element << endl << " Position ▁ : ▁ " << values . position ; return 0 ; }