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.
Programming Praxis 
A simple perl script – if we have a -ve sum we add the first value otherwise subtract the last…
sub splitable { my $s=0; $s+=$s<0?pop@_:-shift@_ while @_; return $s?0:1; }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.
(import (scheme base) (scheme write) (only (srfi 1) fold split-at iota filter-map) (srfi 8)) (define input-101 '(1 2 3 4 5 15)) ;; reverse of: sum of all prefixes of lst (including empty prefix) (define (reverse-prefix-sum/e lst) (fold (lambda (n psums) (cons (+ n (car psums)) psums)) '(0) lst)) ;; ((prefix suffix) ...) such that sum of prefix elements and sum of ;; suffix elements are equal. (define (split*/eq-sum lst) (let ((eq-indices (filter-map (lambda (i x y) (and (= x y) i)) (iota (length lst)) (reverse (reverse-prefix-sum/e lst)) (reverse-prefix-sum/e (reverse lst))))) (map (lambda (i) (receive (l r) (split-at lst i) (list l r))) eq-indices))) ;; examples (display (split*/eq-sum input-101)) (newline) (display (split*/eq-sum (cons 3 input-101))) (newline) (display (split*/eq-sum '(1 2 3 0 -1 -2 6 0 3))) (newline) (display (split*/eq-sum '(1 2 0 3 0 0 -1 -2 6 -2 0 -1 0 2 -2))) (newline)Here’s a solution in Python 3.
import itertools def split_array(l): s = sum(l) for idx, x in enumerate(itertools.accumulate(l), 1): if s - x == x: return l[:idx], l[idx:] return None l = [1, 2, 3, 4, 5, 15] print(split_array(l))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.
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> // The return value indicates success/failure. // The index of the split is saved in out parameter split_idx. bool split_array(int* array, size_t n, size_t* split_idx) { long sum = 0; for (size_t i = 0; i < n; ++i) sum += array[i]; // If sum is odd, there is no valid split. if (sum & 1) return false; long cumsum = 0; for (size_t i = 0; i < n; ++i) { cumsum += array[i]; long remsum = sum - cumsum; // remaining sum if (remsum == cumsum) { *split_idx = i + 1; return true; } // If cumulative sum is greater than remaining // sum, there is no valid split. if (remsum < cumsum) return false; } return false; } void print_array(int* array, size_t n) { printf("["); for (size_t i = 0; i < n; ++i) { if (i > 0) printf(", "); printf("%d", array[i]); } printf("]"); } int main(void) { int array[] = {1, 2, 3, 4, 5, 15}; size_t n = sizeof(array) / sizeof(int); size_t split_idx; int success = split_array(array, n, &split_idx); if (success) { print_array(array, split_idx); printf("\n"); print_array(array + split_idx, n - split_idx); printf("\n"); } else { printf("none\n"); } return EXIT_SUCCESS; }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.
-- Let xs = [x0, x1, x2, ..., xn] and xs[i,j] = xi+x(i+1)+...+xj. -- -- We have xs[0,i] + xs[i+1,n] == xs[0,n], for 0 ≤ i < n. -- -- So, finding an i such that xs[0,i] == xs[i+1,n] is equivalent to finding -- an i such that 2*xs[0,i] == xs[0,n]. -- -- If we let si = xs[0,i] then this can be stated as finding an i such that -- 2*si == sn, 0 ≤ i < n. Note that for i to exist sn must be even. -- -- If all xs are positive then s0, s1, ..., sn is a strictly increasing -- sequence, so we need only consider the si in order, until si equals or -- exceeds sn/2. If si == sn/2 then ([x0, ..., xi], [x(i+1), ..., xn]) is -- a valid partition, otherwise there is none. import Data.Bool import Data.Vector (Vector) import qualified Data.Vector as V equalSplit :: Integral a => Vector a -> Maybe (Vector a, Vector a) equalSplit xs | V.null xs = Nothing | otherwise = let (ss, sn) = (V.postscanl' (+) 0 xs, V.last ss) in if odd sn then Nothing else splIdx (sn `div` 2) ss >>= \i -> Just $ V.splitAt i xs splIdx :: Ord a => a -> Vector a -> Maybe Int splIdx sn ss = let (i, ge) = V.head $ V.dropWhile ((< sn) . snd) $ V.indexed ss in bool Nothing (Just $ i + 1) (ge == sn) test :: [Int] -> IO () test = print . equalSplit . V.fromList main :: IO () main = do test [] test [1] test [1, 2] test [1, 2, 3, 4, 5, 14] test [1, 2, 3, 4, 5, 15] test [1, 2, 3, 2, 3, 1]