## Minimum Split

### December 4, 2015

Today’s task is a simple exercise in list handling:

Given a list of integers, find the place where the list can be split in two that minimizes the differences in the sums of the two halves of the list. For instance, given the list [3,7,4,2,1], splitting after the second element of the list gives sums of 10 and 7 for the two halves of the list, for a difference of 3, and no other split gives a lower difference.

Your task is to write a program that splits a list as indicated above. 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

In Python

It’s not very clear whether this means the minimum difference, or the minimum absolute value of the difference. The wording of page 2 suggests the latter, but page 1 doesn’t say so.

Haskell:

Python:

def bestSplit(lst):

diff = 100000000

idx = 0

for count in range(0, len(lst)):

if diff > abs(sum(lst[:count], 0) – sum(lst[count:], count)):

diff = abs(sum(lst[:count], 0) – sum(lst[count:], count))

idx = count

return idx

Solution in Python

Third attempt in posting the code :p

In Python.

C++ attempt

#include “math.h”

#include

std::vector numberList;

numberList.push_back(3);

numberList.push_back(7);

numberList.push_back(4);

numberList.push_back(2);

numberList.push_back(1);

std::vector differences;

for(int split = 0; split < numberList.size(); ++split)

{

int leftSum = 0;

for(int left = 0; left < split; ++left) {

leftSum += numberList[left];

}

int rightSum = 0;

for(int right = split; right < numberList.size(); ++right) {

rightSum += numberList[right];

}

int difference = abs(rightSum – leftSum);

differences.push_back(difference);

}

int lowestDiffIndex = 0;

int lowestDiffValue = differences[0];

for(int i = 0; i < differences.size(); ++i)

{

lowestDiffIndex = (differences[i] < lowestDiffValue) ? i : lowestDiffIndex;

lowestDiffValue = (differences[i] < lowestDiffValue) ? differences[i] : lowestDiffValue;

}

// Split is at element lowestDiffIndex

A solution in Racket.