20
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Deleted sandbox post \$\endgroup\$ – the default. May 2 at 12:25
  • 1
    \$\begingroup\$ Can you add [1, 2, 4, 8, 14] -> 4 to the test cases \$\endgroup\$ – streetster May 2 at 17:13
  • 1
    \$\begingroup\$ Needs a worked example or two. \$\endgroup\$ – Shaggy May 2 at 19:27
  • 1
    \$\begingroup\$ @Kaddath yes (the question also mentions that in the beginning) \$\endgroup\$ – the default. May 4 at 9:16
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Wheat Wizard May 7 at 3:51

25 Answers 25

13
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Surculose Sputum May 2 at 13:32
  • \$\begingroup\$ @SurculoseSputum that is a nice explanation, I arrived there by rearranging some inequalities. \$\endgroup\$ – ovs May 2 at 13:47
6
\$\begingroup\$

K4 / K (oK), 22 18 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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ What about for [1 2 4 8 14]? It seems that your current solution returns 3 when it should return 4 \$\endgroup\$ – math junkie May 2 at 16:06
  • 1
    \$\begingroup\$ Ta, reverted :) \$\endgroup\$ – streetster May 2 at 17:13
6
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Haskell, 65 36 bytes

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

Try it online!

This answer really just uses one trick. Instead of caluclating

$$ \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} $$

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Pyth, 14 12 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – isaacg May 3 at 18:28
  • \$\begingroup\$ @isaacg Awesome, thanks! \$\endgroup\$ – math junkie May 3 at 18:31
5
\$\begingroup\$

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]
     Ḣ - head                        3
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is very nice, but I think you should return one cut index. \$\endgroup\$ – the default. May 4 at 1:48
  • \$\begingroup\$ 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.') \$\endgroup\$ – Jonathan Allan May 4 at 11:38
  • \$\begingroup\$ ...and doable with 0 bytes :) \$\endgroup\$ – Jonathan Allan May 4 at 11:39
  • \$\begingroup\$ 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 :( ) \$\endgroup\$ – the default. May 4 at 11:40
  • \$\begingroup\$ Fair enough. You did put "2 or 3" not "2 or 3 or [2,3]". I just read "any" and assumed it was fine. \$\endgroup\$ – Jonathan Allan May 4 at 11:43
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

J, 16 13 bytes

-3 bytes thanks to Jonah

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

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Very nice, Galen \$\endgroup\$ – Jonah May 2 at 15:10
  • 1
    \$\begingroup\$ 13 bytes: 1 i.~+/\>+/\. \$\endgroup\$ – Jonah May 2 at 15:13
  • 1
    \$\begingroup\$ @Jonah Thank you! My intention was to use suffix too, but apparently I went another direction :) \$\endgroup\$ – Galen Ivanov May 2 at 16:16
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hah - was just about to ask whether porting mine would be shorter :) \$\endgroup\$ – streetster May 2 at 14:58
  • 1
    \$\begingroup\$ @streetster yup; and I'm sure if I'm clever enough I can make your port even shorter :) \$\endgroup\$ – RGS May 2 at 14:59
  • \$\begingroup\$ How'd you learn APL? \$\endgroup\$ – S.S. Anne May 2 at 18:37
  • \$\begingroup\$ @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! \$\endgroup\$ – RGS May 2 at 19:01
2
\$\begingroup\$

Charcoal, 14 bytes

IΣEθ‹Σ…θ⊕κΣ✂θκ

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
  E             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
I               Cast to string
                Implicitly print
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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, İ. \$\endgroup\$ – Jonathan Allan May 3 at 18:38
  • \$\begingroup\$ @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! \$\endgroup\$ – minhnhat0902 May 4 at 2:55
  • \$\begingroup\$ 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). \$\endgroup\$ – Jonathan Allan May 4 at 11:55
2
\$\begingroup\$

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.
   ć         Head extract,
    s        Put head in the back,
     ˜       Flatten.
      OsO    Sum head & tail.
         α}  Absolute difference between these parts.
           ¬ Take the first item of this sorting.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I like that 8-byter. I personally had this 9-byter in mind when I read the challenge: .œ2ùOÆÄWk. :) \$\endgroup\$ – Kevin Cruijssen May 6 at 8:54
  • \$\begingroup\$ Here an alternative 8-byter based on the 6-byte Jelly answer (1-based indexing): .¥·IOαWk \$\endgroup\$ – Kevin Cruijssen May 6 at 8:59
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 57 bytes using some pattern matching: tio.run/##y00syUjNTSzJTE78n277X1nNwcG/… \$\endgroup\$ – Kyle Miller May 5 at 2:29
  • \$\begingroup\$ 56 bytes by using the second argument of Ordering: Try it online! \$\endgroup\$ – the default. May 5 at 6:04
  • \$\begingroup\$ @mypronounismonicareinstate I guess you accept this type of output since this is your challenge ;) \$\endgroup\$ – J42161217 May 5 at 6:15
  • \$\begingroup\$ 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) \$\endgroup\$ – the default. May 5 at 6:16
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Haskell, 101 85 bytes

f x=snd$minimum$(`zip`[0..])$(\(a,b)->abs$sum a-sum b).(`splitAt`x)<$>[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)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Your let could be replaced with a pattern guard. Try it online! \$\endgroup\$ – Wheat Wizard May 2 at 23:59
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Wheat Wizard May 3 at 0:08
  • \$\begingroup\$ changed it to a zip which I think is what you were getting at but looks like you had a better idea! \$\endgroup\$ – Steven Fontanella May 3 at 2:23
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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)}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – Khuldraeseth na'Barya May 5 at 19:27
  • \$\begingroup\$ Thank you for pointing this out to me - i updated the answer accordingly. \$\endgroup\$ – noAnton May 5 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.