Given an array of n positive integers. Find a minimum positive element to be added to one of the indexes in the array such that it can be partitioned into two contiguous sub-arrays of equal sums. Output the minimum element to be added and the position where it is to be added. If multiple positions are possible then return the least one.
Examples:
Input : arr[] = { 10, 1, 2, 3, 4 }
Output : 0 0
Explanation: The array can already be partitioned into two contiguous subarrays i.e. {10} and {1, 2, 3, 4} with equal sums. So we need to add 0 at any position. (least position is 0)
Input : arr[] = { 5, 4 }
Output : 1 1
Explanation: We need to add 1 to 4 so that two sub arrays are {5},{5} hence output is 1 1 (minimum element and it’s position where it is to be added.
Prerequisites: Prefix Sums
Method 1 (Simple): A naive approach is to calculate the sum of elements from (arr[0] to arr[i]) and (arr[i+1] to arr[n-1]), and at each step find the difference between these two sums, minimum difference will give the element to be added.
Method 2 (Efficient): Careful analysis suggests that we can use the concept of prefix sums and suffix sums. Calculate both of them and find the absolute difference between prefixSum[i] (where prefixSum[i] is the sum of array elements upto ith position) and suffixSum[i + 1] (where suffixSum[i + 1] is the sum of array elements from (i + 1)th position to last position).
For e.g.
arr 10 1 2 3 4 prefixSum 10 11 13 16 20 suffixSum 20 10 9 7 4 Absolute difference between suffixSum[i + 1] and prefixSum[i] 10 - 10 = 0 // minimum 11 - 9 = 1 13 - 7 = 6 16 - 4 = 12 Thus, minimum element is 0, for position, if prefixSum[i] is greater than suffixSum[i + 1], then position is "i + 1". else it's is "i".
Below is the implementation of above approach.
C++
// CPP Program to find the minimum element to // be added such that the array can be partitioned // into two contiguous subarrays with equal sums #include <bits/stdc++.h> using namespace std; // Structure to store the minimum element // and its position struct data { int element; int position; }; struct data findMinElement( int arr[], int n) { struct data result; // initialize prefix and suffix sum arrays with 0 int prefixSum[n] = { 0 }; int suffixSum[n] = { 0 }; prefixSum[0] = arr[0]; for ( int i = 1; i < n; i++) { // add current element to Sum prefixSum[i] = prefixSum[i - 1] + arr[i]; } suffixSum[n - 1] = arr[n - 1]; for ( int i = n - 2; i >= 0; i--) { // add current element to Sum suffixSum[i] = suffixSum[i + 1] + arr[i]; } // initialize the minimum element to be a large value int min = suffixSum[0]; int pos; for ( int i = 0; i < n - 1; i++) { // check for the minimum absolute difference // between current prefix sum and the next // suffix sum element if ( abs (suffixSum[i + 1] - prefixSum[i]) < min) { min = abs (suffixSum[i + 1] - prefixSum[i]); // if prefixsum has a greater value then position // is the next element, else it's the same element. if (suffixSum[i + 1] < prefixSum[i]) pos = i + 1; else pos = i; } } // return the data in struct. result.element = min; result.position = pos; return result; } // Driver Code 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; } |
Java
// Java Program to find the minimum element to // be added such that the array can be partitioned // into two contiguous subarrays with equal sums import java.util.*; class GFG { // Structure to store the minimum element // and its position static class data { int element; int position; }; static data findMinElement( int arr[], int n) { data result= new data(); // initialize prefix and suffix sum arrays with 0 int []prefixSum = new int [n]; int []suffixSum = new int [n]; prefixSum[ 0 ] = arr[ 0 ]; for ( int i = 1 ; i < n; i++) { // add current element to Sum prefixSum[i] = prefixSum[i - 1 ] + arr[i]; } suffixSum[n - 1 ] = arr[n - 1 ]; for ( int i = n - 2 ; i >= 0 ; i--) { // add current element to Sum suffixSum[i] = suffixSum[i + 1 ] + arr[i]; } // initialize the minimum element to be a large value int min = suffixSum[ 0 ]; int pos= 0 ; for ( int i = 0 ; i < n - 1 ; i++) { // check for the minimum absolute difference // between current prefix sum and the next // suffix sum element if (Math.abs(suffixSum[i + 1 ] - prefixSum[i]) < min) { min = Math.abs(suffixSum[i + 1 ] - prefixSum[i]); // if prefixsum has a greater value then position // is the next element, else it's the same element. if (suffixSum[i + 1 ] < prefixSum[i]) pos = i + 1 ; else pos = i; } } // return the data in struct. result.element = min; result.position = pos; return result; } // Driver Code public static void main(String[] args) { int arr[] = { 10 , 1 , 2 , 3 , 4 }; int n = arr.length; data values; values = findMinElement(arr, n); System.out.println( "Minimum element : " + values.element + "\nPosition : " + values.position); } } // This code is contributed by Rajput-Ji |
Python3
# Python Program to find the minimum element to # be added such that the array can be partitioned # into two contiguous subarrays with equal sums # Class to store the minimum element # and its position class Data: def __init__( self ): self .element = - 1 self .position = - 1 def findMinElement(arr, n): result = Data() # initialize prefix and suffix sum arrays with 0 prefixSum = [ 0 ] * n suffixSum = [ 0 ] * n prefixSum[ 0 ] = arr[ 0 ] for i in range ( 1 , n): # add current element to Sum prefixSum[i] = prefixSum[i - 1 ] + arr[i]\ suffixSum[n - 1 ] = arr[n - 1 ] for i in range (n - 2 , - 1 , - 1 ): # add current element to Sum suffixSum[i] = suffixSum[i + 1 ] + arr[i] # initialize the minimum element to be a large value mini = suffixSum[ 0 ] pos = 0 for i in range (n - 1 ): # check for the minimum absolute difference # between current prefix sum and the next # suffix sum element if abs (suffixSum[i + 1 ] - prefixSum[i]) < mini: mini = abs (suffixSum[i + 1 ] - prefixSum[i]) # if prefixsum has a greater value then position # is the next element, else it's the same element. if suffixSum[i + 1 ] < prefixSum[i]: pos = i + 1 else : pos = i # return the data in class. result.element = mini result.position = pos return result # Driver Code if __name__ = = "__main__" : arr = [ 10 , 1 , 2 , 3 , 4 ] n = len (arr) values = Data() values = findMinElement(arr, n) print ( "Minimum element :" , values.element, "\nPosition :" , values.position) # This code is contributed by # sanjeev2552 |
C#
// C# Program to find the minimum element // to be added such that the array can be // partitioned into two contiguous subarrays // with equal sums using System; class GFG { // Structure to store the minimum element // and its position public class data { public int element; public int position; }; static data findMinElement( int []arr, int n) { data result = new data(); // initialize prefix and suffix // sum arrays with 0 int []prefixSum = new int [n]; int []suffixSum = new int [n]; prefixSum[0] = arr[0]; for ( int i = 1; i < n; i++) { // add current element to Sum prefixSum[i] = prefixSum[i - 1] + arr[i]; } suffixSum[n - 1] = arr[n - 1]; for ( int i = n - 2; i >= 0; i--) { // add current element to Sum suffixSum[i] = suffixSum[i + 1] + arr[i]; } // initialize the minimum element // to be a large value int min = suffixSum[0]; int pos = 0; for ( int i = 0; i < n - 1; i++) { // check for the minimum absolute difference // between current prefix sum and the next // suffix sum element if (Math.Abs(suffixSum[i + 1] - prefixSum[i]) < min) { min = Math.Abs(suffixSum[i + 1] - prefixSum[i]); // if prefixsum has a greater value then position // is the next element, else it's the same element. if (suffixSum[i + 1] < prefixSum[i]) pos = i + 1; else pos = i; } } // return the data in struct. result.element = min; result.position = pos; return result; } // Driver Code public static void Main(String[] args) { int []arr = { 10, 1, 2, 3, 4 }; int n = arr.Length; data values; values = findMinElement(arr, n); Console.WriteLine( "Minimum element : " + values.element + "\nPosition : " + values.position); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript 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 class data { constructor(element, position){ this .element = element; this .position = position; } }; function findMinElement(arr, n) { let result = new data(); // initialize prefix and suffix sum arrays with 0 let prefixSum = new Array(n); let suffixSum = new Array(n); prefixSum[0] = arr[0]; for (let i = 1; i < n; i++) { // add current element to Sum prefixSum[i] = prefixSum[i - 1] + arr[i]; } suffixSum[n - 1] = arr[n - 1]; for (let i = n - 2; i >= 0; i--) { // add current element to Sum suffixSum[i] = suffixSum[i + 1] + arr[i]; } // initialize the minimum element to be a large value let min = suffixSum[0]; let pos=0; for (let i = 0; i < n - 1; i++) { // check for the minimum absolute difference // between current prefix sum and the next // suffix sum element if (Math.abs(suffixSum[i + 1] - prefixSum[i]) < min) { min = Math.abs(suffixSum[i + 1] - prefixSum[i]); // if prefixsum has a greater value then position // is the next element, else it's the same element. if (suffixSum[i + 1] < prefixSum[i]) pos = i + 1; else pos = i; } } // return the data in struct. result.element = min; result.position = pos; return result; } // Driver Code let arr = [ 10, 1, 2, 3, 4 ]; let n = arr.length; let values; values = findMinElement(arr, n); document.write( "Minimum element : " + values.element + "<br>Position : " + values.position); // This code is contributed by _saurabh_jaiswal </script> |
Minimum element : 0 Position : 0
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!