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.

Advertisements

Pages: 1 2

8 Responses to “Split An Array”

  1. 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;
    }
    
  2. chaw said

    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)
    
    (((1 2 3 4 5) (15)))
    ()
    (((1 2 3) (0 -1 -2 6 0 3)) ((1 2 3 0) (-1 -2 6 0 3)))
    (((1 2) (0 3 0 0 -1 -2 6 -2 0 -1 0 2 -2))
     ((1 2 0) (3 0 0 -1 -2 6 -2 0 -1 0 2 -2))
     ((1 2 0 3 0 0 -1 -2) (6 -2 0 -1 0 2 -2)))
    

  3. Daniel said

    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:

    ([1, 2, 3, 4, 5], [15])
    
  4. Caz Brunnen said

    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));

  5. Craig S. List said

    @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]

  6. Daniel said

    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:

    [1, 2, 3, 4, 5]
    [15]
    
  7. matthew said

    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.

  8. Globules said

    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]
    
    $ ./splitarr 
    Nothing
    Nothing
    Nothing
    Nothing
    Just ([1,2,3,4,5],[15])
    Just ([1,2,3],[2,3,1])
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: