Partitioning into two contiguous element subarrays with equal sums

Problem

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. Solve using java and dynamic programming concepts.

Examples

input: {1, 2, 3, 6}

output: 0 0

Explanation: 1 + 2 + 3 = 6, so no need to add any elements, can just add 0 in 0 index (doesn't change sums)

input: {5, 4, 9, 7, 3, 4, 7, 8, 1}

output: 4 2

Explanation: 5 + 4 + 9 + 7 = (2) + 3 + 4 + 7 + 8 + 1, need to add 2 to the right hand side to make both sides equal (to 25 in this case)

Solution

Naive: Compute the summation from 0 to input[i], and input[i+1] to input[n-1] and keep track of the minimum value and current index. The naive solution is slow, as you must compute the same summations many times, and step through the whole array just to compute 1 value. The final runtime is O(n^2).

Dynamic Programming: Compute the sum from 0 to input[n-1], and store the values in an array to avoid computing them again. Do the same thing again, but compute the sum from input[n-1] to zero (backwards) and store them in a different array.

input:   5     4    9    7     3     4     7     8     1
preSum:  5     9   18   25    28    32    39    47    48
postSum: 48   43   39   30    23    20    16     9     1

Now find the minim difference between the two calculated arrays

Abs difference between postSum[i + 1] and preSum[i]

5  - 43 = 38
9  - 39 = 30
18 - 30 = 12
25 - 23 =  2 // minimum
28 - 20 =  8
32 - 16 = 16
39 -  9 = 30
47 -  1 = 46

Thus, minimum element is 2.

if preSum[i] is greater than postSum[i + 1], then position is "i + 1".

else it's is "i".

Java code

We will need 2 answers, the index and the value, so we will create a class to encapsulate both values and make it easier to handle, instead of returning an array of 2 integers and remembering which index is what.

private class Tuple {
    int index;
    int value;

    Tuple(int value) {
        this.value = value;
    }
}

Now, we need to work on the algorithm to calculate the pre and post sum arrays.

// preSum finds the summation from 0 to i all the way to N
int[] preSum = new int[arr.length];
preSum[0] = arr[0];
for (int x = 1; x < arr.length; x++) {
    preSum[x] = preSum[x - 1] + arr[x];
}

// postSum finds the summations from N-1 to i all the way to index 0
int[] postSum = new int[arr.length];
postSum[arr.length - 1] = arr[arr.length - 1];
for (int x = arr.length - 2; x >= 0; x--) {
    postSum[x] = postSum[x + 1] + arr[x];
}

All that is left is to find the minimum value and the index where the value needs to be placed.

// initialize the tuple to be the total sum of the array
Tuple tuple = new Tuple(postSum[0]);

for (int i = 0; i < arr.length - 1; i++) {
    // abs difference between postSum[i + 1] and preSum[i]
    int diff = Math.abs(preSum[i] - postSum[i + 1]);
    
    if (diff < tuple.value) {
        // found smaller difference
        tuple.value = diff;

        // right < left, add to the right
        if (postSum[i + 1] < preSum[i])
            tuple.index = i + 1;
        else
            // add to left
            tuple.index = i;
    }
}

You can put both code blocks above in a function (in the order they are shown above) and call it.

private Tuple findMin(int[] arr) {
    // find the pre and post sums
    // ...
    // find the min diff value and index
    // ... 
    // return answer
    return tuple;
}

public static void main(String[] args) {
    int[] input = {5, 4, 9, 7, 3, 4, 7, 8, 1};
    Tuple answer = new MainClass().findMin(input);

    System.out.println(answer.index + " " + answer.value);
}