## Split An Array

### January 23, 2018

We have a simple task today, intended for those students just starting a new semester who are learning programming for the first time:

Given an array of positive integers, determine if the array can be split into two pieces, without re-ordering the elements of the array, so that both pieces have the same sum. If it is possible, return the two pieces. If not, you should so indicate. For instance, the array [1, 2, 3, 4, 5, 15] can be split into two pieces, [1, 2, 3, 4, 5] and [15], each with sum 15.

Your task is to write the program to split an array into two pieces with equal sums. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

A simple perl script – if we have a -ve sum we add the first value otherwise subtract the last…

Here is a solution in R7RS Scheme and some SRFI-1 procedures (and SRFI

8 for receive). It finds all prefix-suffix pairs with equal sums. The

main idea is to sum the array left-to-right and right-to-left and look

for equality of elements at complementary positions.

Here’s a solution in Python 3.

Output:

Super simple JavaScript array.slice method

var arr = [1, 2, 3, 4, 5, 15];

console.log(arr.slice(0, 5));

console.log(arr.slice(5));

@Caz: I don’t see how your code might split an array to match the task. It does work for the given example. But I’m sure it’ll fail for arr = [1, 2, 3, 4, 5, 9]

Here’s a solution in C.

The function indicates success or failure with a return value, and passes the index of the split with an out parameter.

It returns early if the sum is odd or if the running sum is greater than the remaining sum.

Output:

No problem today, hope all is well. For this one, if the array elements are all positive (so the cumulative sum is monotonic), then James’ idea of working in from both ends is good – if negative (or zero) elements are allowed, so there might be multiple solutions, can’t think of anything better than chaw’s approach.

Here’s a Haskell version.