## Split An Array

### January 23, 2018

We make two passes through the array, first determining the sum, and then, if the sum is even, splitting the array at the point where the sum is equal to half the sum of the whole array:

(define (split-equal xs) (let ((n (sum xs))) (if (odd? n) #f (let loop ((xs xs) (n (/ n 2)) (ys (list))) (cond ((null? xs) #f) ((zero? n) (values (reverse ys) xs)) ((negative? n) #f) (else (loop (cdr xs) (- n (car xs)) (cons (car xs) ys))))))))

Here are some examples:

> (split-equal '(1 2 3 4 5 6 21)) (1 2 3 4 5 6) (21) > (split-equal '(1 90 50 30 5 3 2 1)) (1 90) (50 30 5 3 2 1) > (split-equal '(50 100 1000)) #f

You can run the program at https://ideone.com/xwkQf3.

Advertisements

Pages: 1 2

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.