# Split a list evenly

You are given a list of at least two positive integers as input. The challenge is to find such a position of a cut that minimizes the absolute difference between the sums of the two parts (to the left and to the right of it). The position should be given as the index of the first element after the cut.

This is tagged , so the shortest answer wins!

## Test cases

These are 0-indexed.

[1, 2, 3] -> 2
[3, 2, 1] -> 1
[1, 5, 3, 2, 4] -> 2 or 3
[1, 2, 4, 8, 16] -> 4
[1, 1, 1, 1, 1] -> 2 or 3
[1, 2, 4, 8, 14] -> 4


For example, for the first test case, if the cut is placed before the second element, the sums of the parts will be 1 and 5 and the absolute difference will be 4, and if the cut is placed before the third element, the sums will be equal and the absolute difference will be 0. Therefore, the correct output is 2 (assuming 0-indexing). If multiple correct outputs exist, you must output one of them.

## Explained examples

Input: [1, 2, 3]

Cut at 0: [] vs [1, 2, 3] -> 0 vs 1+2+3=6, difference is 6
Cut at 1: [1] vs [2, 3] -> 1 vs 2+3=5, difference is 4
Cut at 2: [1, 2] vs [3] -> 1+2=3 vs 3, difference is 0 (minimum)
Cut at 3: [1, 2, 3] vs [] -> 1+2+3=6 vs 0, difference is 6


Input: [1, 2, 4, 8, 14]

Cut at 0: [] vs [1, 2, 4, 8, 14] -> 0 vs 1+2+4+8+14=29, difference is 29
Cut at 1: [1] vs [2, 4, 8, 14] -> 1 vs 2+4+8+14=28, difference is 27
Cut at 2: [1, 2] vs [4, 8, 14] -> 1+2=3 vs 4+8+14=26, difference is 23
Cut at 3: [1, 2, 4] vs [8, 14] -> 1+2+4=7 vs 8+14=22, difference is 15
Cut at 4: [1, 2, 4, 8] vs [14] -> 1+2+4+8=15 vs 14, difference is 1 (minimum)
Cut at 5: [1, 2, 4, 8, 14] vs [] -> 1+2+4+8+14=29 vs 0, difference is 29


Input: [1, 1, 1, 1, 1]

Cut at 0: [] vs [1, 1, 1, 1, 1] -> 0 vs 1+1+1+1+1=5, difference is 5
Cut at 1: [1] vs [1, 1, 1, 1] -> 1 vs 1+1+1+1=4, difference is 3
Cut at 2: [1, 1] vs [1, 1, 1] -> 1+1=2 vs 1+1+1=3, difference is 1 (minimum)
Cut at 3: [1, 1, 1] vs [1, 1] -> 1+1+1=3 vs 1+1=2, difference is 1 (minimum)
Cut at 4: [1, 1, 1, 1] vs [1] -> 1+1+1+1=4 vs 1, difference is 3
Cut at 5: [1, 1, 1, 1, 1] vs [] -> 1+1+1+1+1=5 vs 0, difference is 5

• Deleted sandbox post May 2, 2020 at 12:25
• Can you add [1, 2, 4, 8, 14] -> 4 to the test cases
– mkst
May 2, 2020 at 17:13
• Needs a worked example or two. May 2, 2020 at 19:27
• @Kaddath yes (the question also mentions that in the beginning) May 4, 2020 at 9:16
• @Kaddath If anyone does consider zero positive they are certainly in the extreme minority. Positive is certainly a clear enough term, especially within this site where it has a solid precedent of meaning greater than zero. The confusion usually occurs with the phrase natural number. May 7, 2020 at 3:51

# Python 3, 50 35 bytes

f=lambda a,*l:sum(l)>0and-~f(*l,-a)


Try it online!

### Explanation

If the sum of elements on the left of a is smaller than the sum of elements right of a, then the cut must be after a - explanation by Surculose Sputum.

How I arrived here:

In each recursive call we compare abs(sum(x[:i]) - sum(x[i:])) to abs(sum(x[:i+1]) - sum(x[i+1:])). If the first distance is larger, we continue with the next recursive call, if not the program is stopped:

f=lambda x,i=0:abs(sum(x[:i])-sum(x[i:]))>abs(sum(x[:i+1])-sum(x[i+1:]))and f(x,i+1)


This can be shortened by modifying the list to make the distance calculation simpler:

f=lambda x:abs(sum(x))>abs(sum(x[1:])-x[0])and 1+f(x[1:]+[-x[0]])


Even shorter if we take the input as single arguments:

f=lambda a,*l:abs(sum(x)+a)>abs(sum(x)-a)and 1+f(*x,-a)


By rearranging the formula ...

$$|(\sum_{k \in x}k) + a| > |(\sum_{k \in x}k) - a| \\ \iff ((\sum_{k \in x}k) + a)^2 > ((\sum_{k \in x}k) - a)^2 \\ \iff ((\sum_{k \in x}k) + a)^2 - ((\sum_{k \in x}k) - a)^2 > 0 \\ \iff 4 \cdot (\sum_{k \in x}k) \cdot a > 0 \\ \overset{a>0}\iff \sum_{k \in x}k > 0$$

... we arrive at the final solution:

f=lambda a,*x:sum(x)>0and-~f(*x,-a)

• Brilliant! Took me a while to understand this, here's my attempt at an explanation: If the sum of elements on the left of a is smaller than the sum of elements right of a, then the cut must be after a. Otherwise, stop and returns the index of a. May 2, 2020 at 13:32
• @SurculoseSputum that is a nice explanation, I arrived there by rearranging some inequalities.
– ovs
May 2, 2020 at 13:47

# K4 / K (oK), 2218 14 bytes

Solution:

*&(+\x)>|+\|x:


Try it online!

Explanation:

Compare cumulative sum against reverse of the reverse cumulative sum.

*&(+\x)>|+\|x: / the solution
x: / save input as x
|x  / reverse
+\    / cumulative sum
|      / reverse
>       / greater than?
(+\x)        / cumulative sum x
&             / indices where true
*              / take first

• What about for [1 2 4 8 14]? It seems that your current solution returns 3 when it should return 4 May 2, 2020 at 16:06
• Ta, reverted :)
– mkst
May 2, 2020 at 17:13

# MATL, 13 bytes

t&+gREqY*|&X<


The output is 0-indexed. Try it online! Or verify all test cases.

### Explanation

Consider input [1 2 4 8 16] as an example.

t    % Implicit input. Duplicate
% STACK: [1 2 4 8 16], [1 2 4 8 16]
&+g  % All pair-wise additions, then convert to logical. Gives square matrix of ones
% STACK: [1 2 4 8 16], [1 1 1 1 1;
1 1 1 1 1;
1 1 1 1 1;
1 1 1 1 1;
1 1 1 1 1]
R    % Upper triangular matrix. Sets elements below the diagonal to zero
% STACK: [1 2 4 8 16], [1 1 1 1 1;
0 1 1 1 1;
0 0 1 1 1;
0 0 0 1 1;
0 0 0 0 1]
Eq   % Times 2, minus 1, element-wise
% STACK: [1 2 4 8 16], [ 1  1  1  1  1;
-1  1  1  1  1;
-1 -1  1  1  1;
-1 -1 -1  1  1;
-1 -1 -1 -1  1]
Y*   % Matrix multiplication
% STACK: [-29 -25 -17  -1  31]
|    % Absolute value, element-wise
% STACK: [29 25 17 1 31]
&X<  % Index of minimum entry
% STACK: 4
% Implicit display


(0%)
a%(b:c)|a<sum c=1+(a+b)%c
a%_=0


Try it online!

$$\left|a-b\right|$$ and taking the minimum, go until the left hand side is greater than the right hand side.

To see why this works we will show that:

$$\left|a-(b+c)\right| < \left|(a+b)-c\right| \implies a > c$$

Here is the proof:

$$\begin{matrix} \left|(a-c)-b \right| < \left|(a-c)+b \right| &\implies \\ a - c > 0 &\implies \\ a > c \end{matrix}$$

# Pyth, 1412 11 bytes

-1 byte thanks to @isaacg

lhoaysNsQ._


Try it online!

lhoaysNsQ._
._  All prefixes of input list
o           Sort, using the following function as the key:
a          Absolute difference of
sN        - the sum of the prefix
y              times 2
sQ      - the sum of the input list
h            First such prefix
l             Take its length
(which gives the index of the element immediately after the prefix)


This is based on the following identity:

$$\ \left|\sum_{b \in R} b - (\sum_{q \in Q} q - \sum_{b \in R} b) \right| = \left|2\sum_{b \in R} b - \sum_{q \in Q} q \right|\$$

where $$\R\$$ is the current prefix and $$\Q\$$ is the input list.

• You can save a byte by replacing .m by o and b by N. .m isn't needed if you're going to use h right afterwards. May 3, 2020 at 18:28
• @isaacg Awesome, thanks! May 3, 2020 at 18:31

# Jelly, 6 bytes

ÄḤạSỤḢ


A monadic Link accepting a list which yields the first available cut index.

Try it online!

### How?

ÄḤạSỤḢ - Link: list, X         e.g.  [ 7,  1,  1,  1,  1,  1,  1,  6]
Ä      - cumulative sums (X)         [ 7,  8,  9, 10, 11, 12, 13, 19]
Ḥ     - double                      [14, 16, 18, 20, 22, 24, 26, 38]
S   - sum (X)                     19
ạ    - difference (vectorises)     [ 5,  3,  1,  1,  3,  5,  7, 19]
Ụ  - grade                       [3, 4, 2, 5, 1, 6, 7, 8]

• This is very nice, but I think you should return one cut index. May 4, 2020 at 1:48
• Easily accommodated with one byte, but if this is a requirement you should probably change If multiple correct outputs exist, you can output any. to something like If multiple correct outputs exist, you must output one. ('any: used to refer to one or some of a thing or number of things, no matter how much or how many.') May 4, 2020 at 11:38
• ...and doable with 0 bytes :) May 4, 2020 at 11:39
• I guess I'll do that, but I have seen the exact sentence If multiple correct outputs exist, you can output any used to mean that very many times, and the test cases look like [1, 5, 3, 2, 4] -> 2 or 3, not -> [2, 3] (and the lead also asks for such a position that - I tried to word that to avoid this exact misunderstanding :( ) May 4, 2020 at 11:40
• Fair enough. You did put "2 or 3" not "2 or 3 or [2,3]". I just read "any" and assumed it was fine. May 4, 2020 at 11:43

# Python 3, 67 bytes

lambda l:min([abs(sum(l)-2*sum(l[:i])),i]for i in range(len(l)))[1]


Try it online!

Straightforward implementation, can probably be golfed more. Output the 0-indexed cut.

# J, 16 13 bytes

-3 bytes thanks to Jonah

1 i.~+/\>+/\.


Try it online!

• Very nice, Galen May 2, 2020 at 15:10
• 13 bytes: 1 i.~+/\>+/\. May 2, 2020 at 15:13
• @Jonah Thank you! My intention was to use suffix too, but apparently I went another direction :) May 2, 2020 at 16:16

# JavaScript (ES6),  64  48 bytes

Now very similar to ovs' answer, but we keep track of the left sum in $$\s\$$ rather than re-injecting the opposite values in the list.

f=([v,...a],s=0)=>s<=eval(a.join+)&&1+f(a,s+v)


Try it online!

NB: eval(a.join('+')) is undefined if $$\a[\:]\$$ is empty, so s<=eval(a.join('+')) is always false in that case.

# Husk, 8 bytes

η◄Ṁ≠½Σ¹∫


Try it online!

## Explanation

η◄Ṁ≠½Σ¹∫  Implicit input, say x = [5,2,2,3,6,2,6]
∫  Prefix sums: p = [5,7,9,12,18,20,26]
Σ¹   Sum of x: 26
½     Halve: 13
Ṁ≠      Absolute differences with elements of p: [8,6,4,1,5,7,13]
η◄        1-based index of minimal element: 4


# APL (Dyalog Unicode), 20 SBCS bytes

(⊃∘⍸((+\⌽)≥(⌽+\))∘⌽)


Try it online! Port of streetster's answer so be sure to upvote that one as well. This one is 1-indexed and returns the first option available.

# APL (Dyalog Unicode), 29 SBCS bytes

{0>+/1↓⍵:0⋄1+∇((-1∘↑),⍨1∘↓)⍵}


Try it online! This is 0-indexed and returns the second option, when available. Fairly direct port of ovs's answer so be sure to upvote that answer as well!

• Hah - was just about to ask whether porting mine would be shorter :)
– mkst
May 2, 2020 at 14:58
• @streetster yup; and I'm sure if I'm clever enough I can make your port even shorter :)
– RGS
May 2, 2020 at 14:59
• How'd you learn APL? May 2, 2020 at 18:37
• @S.S.Anne APL Cultivations (chat-based bi-weekly lessons), asking a lot of questions over at the APL Orchard chatroom (and plenty of them answered by a very patient Adám) and tackling problems. Oh, and of course: banging my head against the wall a lot. Also, I am very much a newbie still!
– RGS
May 2, 2020 at 19:01

# Charcoal, 14 bytes

ＩΣＥθ‹Σ…θ⊕κΣ✂θκ


Try it online! Link is to verbose version of code. 0-indexed. Port of @ovs's solution, except that I include the current element in each sum as the sum of an empty list is None. Explanation:

   θ            Input aray
Ｅ             Map over elements
κ      Current index
⊕       Incremented
θ        Input array
…         Sliced to that index
Σ          Take the sum
‹           Is less than
κ  Current index
θ   Input array
✂    Sliced starting at that index
Σ     Take the sum
Σ              Take the sum
Ｉ               Cast to string
Implicitly print


# APL (Dyalog), 25 24 bytes

{(⊢⍳⌊/)|⍵+.×∘.(≤->)⍨⍳⍴⍵}


or

(|⍳⌊/∘|)∘.(≤->)⍨∘⍳∘⍴+.×⊢


Try it online!

Using a variation on @LuisMendo's method.

How?

⍳⍴⍵ gives the range 1 .. n where n is the array size.

∘.(≤->)⍨⎕ performs an outer product with x≤y - x>y (1 for upper triangular, -1 for lower)

⍵+.×⎕ matrix-multiplies with the array

|⎕ does absolute value, and

⎕⍳⌊/⎕ searches the minimum index of the result

# Racket, 71 bytes

(define(f a[s 0][n 0])(if(<(apply + a)s)n(f(cdr a)(+(car a)s)(+ n 1))))


Try it online!

1-indexed

# Jelly, 10 bytes

ḣJ§ạSH$iṂ$


Try it online!

### How?

ḣJ§ạSH$iṂ$ - Main link (with input l, e.g. l = [1, 2, 4, 8, 16])
iṂ$- Get the index of the smallest element of ạ - the absolute difference between SH$        - sum of elements in l divided by 2 and
ḣJ§            - for n in range(1, len(l)), get sum of the first n elements of l, e.g. [1, 3, 7, 15, 31]

• Nice, welcome to CGCC! It turns out that my entry, ÄḤạSİM, is a golfed version of this. ḣJ§ is Ä. Doubling the left, ÄḤ, saves the $ used when halving the right, SH$. I also return all possible indices by finding the maximal indices, M, of the inverse values, İ. May 3, 2020 at 18:38
• @JonathanAllan Interesting. I'm fairly new to Jelly, and there's some quirks that I didn't know, like the Ä. So thank you for your explanation! May 4, 2020 at 2:55
• It does take some time for most people, seems like you're off to a good start so keep going! Also note that there is a chat room for getting better with Jelly (it's not very active, but is used). May 4, 2020 at 11:55

# 05AB1E (legacy), 8 bytes

Port of Zgarb's Husk answer. The index is 0-based.

ηOsO;αWk


Try it online!

# 05AB1E (legacy), 12 bytes

āΣôćs˜OsOα}¬


Try it online!

# Explanation

ā            Length-range with the input.
Σ           Sort by this:
ô          Split input into chunks of current item.
s        Put head in the back,
˜       Flatten.
α}  Absolute difference between these parts.
¬ Take the first item of this sorting.

• I like that 8-byter. I personally had this 9-byter in mind when I read the challenge: .œ2ùOÆÄWk. :) May 6, 2020 at 8:54
• Here an alternative 8-byter based on the 6-byte Jelly answer (1-based indexing): .¥·IOαWk May 6, 2020 at 8:59

# Wolfram Language (Mathematica), 55 bytes

Abs@ReplaceList[#,{x__,y__}:>Plus@x-Plus@y]~Ordering~1&


Try it online!

24 bytes saved @Kyle Miller
2 byte from my @pronoun is monicareinstate

• 57 bytes using some pattern matching: tio.run/##y00syUjNTSzJTE78n277X1nNwcG/… May 5, 2020 at 2:29
• 56 bytes by using the second argument of Ordering: Try it online! May 5, 2020 at 6:04
• @mypronounismonicareinstate I guess you accept this type of output since this is your challenge ;) May 5, 2020 at 6:15
• I have now noticed that ...~Ordering~1 works as well. (that type of output is valid because it's always a single integer, as far as I know) May 5, 2020 at 6:16

# Red, 60 bytes

func[a][s: 0 i: 1
while[(s: s + take a)<= sum a][i: i + 1]i]


Try it online!

1-indexed

# Perl 5 -aple, 39 bytes

my$i;@F=map{(++$i)x$_}@F;$_=$F[$#F/2-1]


Try it online!

...or 42 bytes:

sub f{my$i;@_=map{(++$i)x$_}@_;$_[@_/2-1]}


Try it online!

f x=snd$minimum$(zip[0..])$(\(a,b)->abs$sum a-sum b).(splitAtx)<$>[0..length x-1]  Try it online! Less golfed: minIndex f=snd.minimum.(zip[0..]).map f f x = minIndex inner [0..length x-1] where inner = (\(a, b)->abs$ sum a - sum b) . (splitAt x)

• Your let could be replaced with a pattern guard. Try it online! May 2, 2020 at 23:59
• Also I'm not sure why you map across z just to index by i. Since z is just a range of numbers this is the same as applying the function to i directly which saves a lot of bytes and gets rid of the need for let altogether. May 3, 2020 at 0:08
• changed it to a zip which I think is what you were getting at but looks like you had a better idea! May 3, 2020 at 2:23

# C# (Visual C# Interactive Compiler), 58 49 bytes

Uses a variable declaration via is to avoid declaring a proper body and having to type the excessively long word return.

For some reason List has the method FindIndex, but other IEnumerables don't seem to.

a=>0is var s?a.FindIndex(e=>(s+=e)>a.Sum()-s+e):0


Try it online!

# C (gcc), 112 bytes

l;r;f(int n,char**m){char*i=*(m+1),*j=i;while(*j++);for(j-=2,r=l=0;i<=j;)l<r?l+=*i++:(r+=*j--);return i-*(m+1);}


Try it online!

Unfortunately I did not figure out how to input hex characters as arguments into the program with the online view.
Basically the input consists of a single "argument" which is the array of numbers.

• Welcome to Code Golf SE! We're glad to have you. Looking over this answer, I'm struggling to make sense of it. Admittedly, I'm no C expert, but perhaps a brief explanation of what the arguments and return value are might be in order. If you want to provide an example of your code in action, check out Try It Online, created by our very own Dennis; it makes writing, testing, and sharing code very easy, even to the point of copying an entire well-formatted Code Golf SE submission to your clipboard automatically! May 5, 2020 at 19:27
• Thank you for pointing this out to me - i updated the answer accordingly. May 5, 2020 at 21:54

# Desmos, 69 66 bytes

f(l)=L[∑_{n=1}^Ll[n]>=∑_{k=L}^{L.max}l[k]][1]
L=[1...l.length]


Returns 1-based indices. Uses the same strategy as ovs's Python answer

Try It On Desmos!

Try It On Desmos! - Prettified

# Scala, 117 bytes

def g(l:List[Int],s:Int,i:Int):Int={val h::t=l;if(t==Nil)i else if(s+h>t.sum)if(s<l.sum)i+1 else i else g(t,s+h,i+1)}


This question deserved a lengthy suboptimal PHP answer, that has to cope with the fact that the arguments array starts with the script name, forcing me to add the $i>1 test that leads to extra brackets, and such oddities.. # PHP, 124 bytes $f=array_sum;$g=array_slice;for($a=$argv;$a[++$i];$s=$r)if(($s<$r=abs($f($g($a,$i))-$f($g($a,0,$i))))&$i>1)break;echo(\$i-2);


Try it online!

# Java (JDK), 84 bytes

a->{int i=0,j=a.length-1,l=0,r=0,t;for(;i<j;)t=l<r?l+=a[i++]:(r+=a[j--]);return-~i;}


Try it online!

## Credits

• 82 bytes May 5, 2020 at 22:24