Code Golf Asked by Zgarb on November 10, 2020

Consider a nonempty list **L** of integers.

A *zero-sum slice* of **L** is a contiguous subsequence of **L** whose sum equals 0.

For example, **[1, -3, 2]** is a zero-sum slice of **[-2, 4, 1, -3, 2, 2, -1, -1]**, but **[2, 2]** is not (because it doesn’t sum to 0), and neither is **[4, -3, -1]** (because it’s not contiguous).

A collection of zero-sum slices of **L** is a *zero-sum cover* of **L** if every element belongs to at least one of the slices.

For example:

```
L = [-2, 4, 1, -3, 2, 2, -1, -1]
A = [-2, 4, 1, -3]
B = [1, -3, 2]
C = [2, -1, -1]
```

The three zero-sum slices **A**, **B** and **C** form a zero-sum cover of **L**.

Multiple copies of the same slice can appear in a zero-sum cover, like this:

```
L = [2, -1, -1, -1, 2, -1, -1]
A = [2, -1, -1]
B = [-1, -1, 2]
C = [2, -1, -1]
```

Of course, not all lists have a zero-sum cover; some examples are **[2, -1]** (every slice has nonzero sum) and **[2, 2, -1, -1, 0, 1]** (the leftmost **2** is not part of a zero-sum slice).

Your input is a nonempty integer list **L**, taken in any reasonable format.

Your output shall be a truthy value if **L** has a zero-sum cover, and a falsy value if not.

You can write a full program or a function, and the lowest byte count wins.

```
[-1] -> False
[2,-1] -> False
[2,2,-1,-1,0,1] -> False
[2,-2,1,2,-2,-2,4] -> False
[3,-5,-2,0,-3,-2,-1,-2,0,-2] -> False
[-2,6,3,-3,-3,-3,1,2,2,-2,-5,1] -> False
[5,-8,2,-1,-7,-4,4,1,-8,2,-1,-3,-3,-3,5,1] -> False
[-8,-8,4,1,3,10,9,-11,4,4,10,-2,-3,4,-10,-3,-5,0,6,9,7,-5,-3,-3] -> False
[10,8,6,-4,-2,-10,1,1,-5,-11,-3,4,11,6,-3,-4,-3,-9,-11,-12,-4,7,-10,-4] -> False
[0] -> True
[4,-2,-2] -> True
[2,2,-3,1,-2,3,1] -> True
[5,-3,-1,-2,1,5,-4] -> True
[2,-1,-1,-1,2,-1,-1] -> True
[-2,4,1,-3,2,2,-1,-1] -> True
[-4,-1,-1,6,3,6,-5,1,-5,-4,5,3] -> True
[-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3] -> True
[4,-9,12,12,-11,-11,9,-4,8,5,-10,-6,2,-9,10,-11,-9,-2,8,4,-11,7,12,-5] -> True
```

```
≢={≢∪∊↓∘⍳/¨⍸∘.=⍨0,+⍵}
```

Same byte count as Jo King's, but totally different approach.

```
≢={≢∪∊↓∘⍳/¨⍸∘.=⍨0,+⍵} ⍝ Input: integer vector
{ 0,+⍵} ⍝ Cumulative sum and prepend 0
∘.=⍨ ⍝ Self outer product by equality
⍸ ⍝ Extract coords of ones; (a,b) with a>b is included
⍝ iff the interval [b+1..a] has zero sum
↓∘⍳/¨ ⍝ For each coord, [b+1..a] if a>b, empty vector otherwise
≢∪∊ ⍝ Count unique values
≢= ⍝ Is the count same as the length of the original array?
```

Answered by Bubbler on November 10, 2020

```
lambda a,r=range:len({k for j in r(len(a)+1)for i in r(j)if sum(a[i:j])==0for k in r(i,j)})==len(a)
```

Creates a set of all indices which are part of a zero sum. Then checks if all indices are present.

Answered by Jitse on November 10, 2020

*-2 bytes thanks to Bubbler*

```
∧/∨⌿↑0={×⌽+⌽⍵}¨,⎕
```

```
,⎕ ⍝ All prefixes of the input
{ }¨ ⍝ Map each to
⌽+⌽⍵ ⍝ The sum of each postfix
× ⍝ Scan multiplied, spreading any zero sums to the other elements in the sub-array
0= ⍝ Map zeroes to true
↑ ⍝ Mix the arrays into a 2D matrix
∧/∨⌿ ⍝ Do all columns have at least one true value?
```

Answered by Jo King on November 10, 2020

```
a=>(g=f=>a.map((_,i)=>f(i)))(i=>g(j=>j<i||(t+=a[j])||g(k=>b[k]&=k<i|k>j),t=0),b=g(_=>1))&&!/1/.test(b)
```

Computes the partial sums for all the elements `i..j`

inclusive, and resets the relevant elements of `b`

from `1`

to `0`

when it finds a zero sum, finally checking that there are no `1`

s left.

Answered by Neil on November 10, 2020

Brute force and still over 99 bytes. :-(

```
for($p=$r=$c=$argc;$s=--$p;)for($i=$c;$s&&$k=--$i;)for($s=0;$k<$c&&($r-=!$s+=$argv[$k++])&&$s;);echo!$r;
```

takes input from command line arguments, `1`

for truthy, empty for falsy. Run with `-r`

.

**breakdown**

```
for($p=$r=$argc;$s=$p--;) # loop $p from $argc-1 to 0 with dummy value >0 for $s
for($i=$p;$s&&$k=$i--;) # loop $i (slice start) from $p to 1, break if sum is 0
for($s=0; # init sum to 0
$k<$argc # loop $k (slice end) from $i to $argc-1
&&($r-=!$s+=$argv[$k++]) # update sum, decrement $r if sum is 0
&&$s;); # break loop if sum is 0
echo!$r; # $r = number of elements that are not part of a zero-sum slice
```

`$argv[0]`

contains the filename; if run with `-r`

, it will be `-`

and evaluate to `0`

for numeric ops.

Answered by Titus on November 10, 2020

```
#(=(count %)(count(set(flatten(for[r[(range(count %))]l r p(partition l 1 r):when(=(apply +(map % p))0)]p))))
```

Generates all partitions which sum to zero, checks that it has "length of input vector" distinct indices.

Answered by NikoNyrh on November 10, 2020

```
#*/@e.[:;]({:*0=[:+/{.)@|:.@,.#
```

For every subsum I add the element's indexes and I keep the indexes iff subsum is `0`

and then check whether every index is present.

Trick: 1-based indexes of a list can be generated with `#`

i.e. length of every prefix.

Usage:

```
(#*/@e.[:;]({:*0=[:+/{.)@|:.@,.#) 2 _1 _1 2
1
(#*/@e.[:;]({:*0=[:+/{.)@|:.@,.#) 2 _1
0
```

Answered by randomra on November 10, 2020

```
def f(l):
r=range(len(l))
if[i for i in r for j in r if sum(l[j:j+i+1])==0]:return 1
```

Truthy = 1 Falsy = None

Answered by sonrad10 on November 10, 2020

```
import Data.Lists
g x=(1<$x)==(1<$nub(id=<<[i|(i,0)<-fmap sum.unzip<$>powerslice(zip[1..]x)]))
```

Usage example: ```
g [-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3]
```

-> `True`

.

How it works (let's use `[-1,1,5,-5]`

for input):

```
zip[1..]x -- zip each element with its index
-- -> [(1,-1),(2,1),(3,5),(4,-5)]
powerslice -- make a list of all continuous subsequences
-- -> [[],[(1,-1)],[(1,-1),(2,1)],[(1,-1),(2,1),(3,5)],[(1,-1),(2,1),(3,5),(4,-5)],[(2,1)],[(2,1),(3,5)],[(2,1),(3,5),(4,-5)],[(3,5)],[(3,5),(4,-5)],[(4,-5)]]
<$> -- for each subsequence
unzip -- turn the list of pairs into a pair of lists
-- -> [([],[]),([1],[-1]),([1,2],[-1,1]),([1,2,3],[-1,1,5]),([1,2,3,4],[-1,1,5,-5]),([2],[1]),([2,3],[1,5]),([2,3,4],[1,5,-5]),([3],[5]),([3,4],[5,-5]),([4],[-5])]
fmap sum -- and sum the second element
-- -> [([],0),([1],-1),([1,2],0),([1,2,3],5),([1,2,3,4],0),([2],1),([2,3],6),([2,3,4],1),([3],5),([3,4],0),([4],-5)]
[i|(i,0)<- ] -- take all list of indices where the corresponding sum == 0
-- -> [[],[1,2],[1,2,3,4],[3,4]]
id=<< -- flatten the list
-- -> [1,2,1,2,3,4,3,4]
nub -- remove duplicates
-- -> [1,2,3,4]
(1<$x)==(1<$ ) -- check if the above list has the same length as the input list.
```

Answered by nimi on November 10, 2020

_{-3 bytes thanks to @Zgarb}

Populates a list with the same size as the input with zero-sum slices and overwrites according to indexes, returning its equality to the original at the end.

```
def f(l):
s=len(l);n=[0]*s
for i in range(s):
for j in range(i,s+1):
if sum(l[i:j])==0:n[i:j]=l[i:j]
return n==l
```

Answered by dfernan on November 10, 2020

```
f=([q,...a],b=[],c=[])=>1/q?f(a,[...b,0].map((x,i)=>x+q||(c=c.map((n,j)=>n|i<=j)),c.push(0)),c):c.every(x=>x)
```

```
f=([q,...a],b=[],c=[])=>1/q?f(a,[...b,0].map((x,i)=>x+q||(c=c.map((n,j)=>n|i<=j)),c.push(0)),c):c.every(x=>x)
I.textContent = I.textContent.replace(/.+/g,x=>x+` (${f(eval(x.split(" ")[0]))})`)
```

```
<pre id=I>[-1] -> False
[2,-1] -> False
[2,2,-1,-1,0,1] -> False
[2,-2,1,2,-2,-2,4] -> False
[3,-5,-2,0,-3,-2,-1,-2,0,-2] -> False
[-2,6,3,-3,-3,-3,1,2,2,-2,-5,1] -> False
[5,-8,2,-1,-7,-4,4,1,-8,2,-1,-3,-3,-3,5,1] -> False
[-8,-8,4,1,3,10,9,-11,4,4,10,-2,-3,4,-10,-3,-5,0,6,9,7,-5,-3,-3] -> False
[10,8,6,-4,-2,-10,1,1,-5,-11,-3,4,11,6,-3,-4,-3,-9,-11,-12,-4,7,-10,-4] -> False
[0] -> True
[4,-2,-2] -> True
[2,2,-3,1,-2,3,1] -> True
[5,-3,-1,-2,1,5,-4] -> True
[2,-1,-1,-1,2,-1,-1] -> True
[-2,4,1,-3,2,2,-1,-1] -> True
[-4,-1,-1,6,3,6,-5,1,-5,-4,5,3] -> True
[-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3] -> True
[4,-9,12,12,-11,-11,9,-4,8,5,-10,-6,2,-9,10,-11,-9,-2,8,4,-11,7,12,-5] -> True</pre>
```

Answered by ETHproductions on November 10, 2020

```
% =>(1 to%.size)flatMap(%sliding)exists(_.sum==0)
```

```
val f:(Seq[Int]=>Boolean)= % =>(1 to%.size)flatMap(%sliding)exists(_.sum==0)
f(Seq(4, -2, -2)) //returns true
```

```
array=>(1 to array.size)
.flatMap(n => array.sliding(n))
.exists(slice => slice.sum == 0)
```

```
% => //define a anonymouns function with a parameter called %
(1 to %.size) //create a range from 1 to the size of %
flatMap( //flatMap each number n of the range
%sliding //to an iterator with all slices of % with length n
)exists( //check whether there's an iterator with a sum of 0
_.sum==0
)
```

Answered by corvus_192 on November 10, 2020

*Thanks to ngenisis for saving 1 byte.*

```
Union@@Cases[Subsequences[x=Range@Tr[1^#]],a_/;Tr@#[[a]]==0]==x&
```

I'd rather find a pure pattern matching solution, but it's proving to be tricky (and things like `{___,a__,___}`

are always super lengthy).

Answered by Martin Ender on November 10, 2020

*Saved 1 byte, and hopefully learned a new trick for the future, thanks to ngenisis!*

Two equally long alternatives, both of which are unnamed functions taking a list of integers as input and returning `True`

or `False`

:

```
And@@Table[0==Product[Tr@#[[i;;j]],{i,k},{j,k,l}],{k,l=Tr[1^#]}]&
0==Norm@Table[Product[Tr@#[[i;;j]],{i,k},{j,k,l}],{k,l=Tr[1^#]}]&
```

In both cases, `Tr@#[[i;;j]]`

computes the sum of the slice of the input from position `i`

to position `j`

(1-indexed). `Product[...,{i,k},{j,k,l}]`

multiples together all these slice-sums, as `i`

ranges over indices that are at most `k`

and `j`

ranges over indices that are at least `k`

. (Note that `l=Tr[1^#]`

defines `l`

to be the sum of `1`

to all the powers in the input list, which is simply the length of the list.) In other words, this product equals 0 if and only if the `k`

th element belongs to a zero-sum slice.

In the first version, each of those products is compared to `0`

, and `And@@`

returns `True`

precisely when every single product equals `0`

. In the second version, the list of products is acted upon by the function `Norm`

(the length of the `l`

-dimensional vector), which equals `0`

if and only if every entry equals `0`

.

Answered by Greg Martin on November 10, 2020

```
JẆịS¥ÐḟċþJḄẠ
```

```
JẆịS¥ÐḟċþJḄẠ Main link. Argument: A (array)
J Yield all indices of A.
Ẇ Window; yield all slices of indices.
Ðḟ Filter; keep slices for which the link to the left returns 0.
¥ Combine the two atoms to the left into a dyadic chain.
ị Retrieve the elements of A at the slice's indices.
S Take the sum.
J Yield the indices of A.
ċþ Count table; count how many times each index appears in each table.
Ḅ Unbinary; convery the array of counts of each index from base 2 to
integer. This yields 0 iff an index does not appear in any slice.
Ạ All; return 1 iff all integers are non-zero.
```

Answered by Dennis on November 10, 2020

Simplistic brute-force solution; for every element of the array, try to find a zero-sum slice that contains it.

```
->a{(0..l=a.size).all?{|i|(0..i).any?{|j|(i..l).any?{|k|a[j..k].inject(:+)==0}}}}
```

Answered by Value Ink on November 10, 2020

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP