40
\$\begingroup\$

Introduction

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

The task

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.

Test cases

[-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
\$\endgroup\$
5
  • \$\begingroup\$ By "every element belongs to one of the slices", are you treating the same value at different indices as distinct? \$\endgroup\$
    – user61980
    Jan 10, 2017 at 15:46
  • \$\begingroup\$ @ngenisis Yes, they are distinct and each should occur in a slice that contains the corresponding index. \$\endgroup\$
    – Zgarb
    Jan 10, 2017 at 16:38
  • 2
    \$\begingroup\$ Should not the third falsy example [2,2,-1,-1,0,1] -> False be truthy since both slices [2,-1,-1] and [-1,0,1] add to zero and all their elements are in the original list? \$\endgroup\$
    – dfernan
    Jan 10, 2017 at 21:33
  • \$\begingroup\$ The leftmost 2 is not part of any zero-sum slice. It's a bit unclear, but they have to occur in a slice that "contains their index". \$\endgroup\$
    – Zgarb
    Jan 10, 2017 at 21:35
  • \$\begingroup\$ Understood. That makes it harder. :o) \$\endgroup\$
    – dfernan
    Jan 10, 2017 at 21:37

16 Answers 16

12
\$\begingroup\$

Jelly, 13 12 bytes

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

Try it online!

How it works

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.
\$\endgroup\$
0
9
\$\begingroup\$

Mathematica, 66 65 bytes

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 kth 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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Tr[1^#] saves 1 byte from Length@#. \$\endgroup\$
    – user61980
    Jan 10, 2017 at 16:10
  • \$\begingroup\$ Would 0^ work instead of 0==? Not sure how Mathematica handles that. (you would return 1/0 instead of true/false) \$\endgroup\$
    – Cyoce
    Jan 10, 2017 at 18:52
  • 1
    \$\begingroup\$ Cool idea, but Mathematica returns Indeterminate for 0^0. Also, 1/0 aren't actually truthy/falsy in Mathematica—it's too strongly typed to make golfers happy :) \$\endgroup\$ Jan 10, 2017 at 22:03
7
\$\begingroup\$

Mathematica, 65 64 bytes

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

\$\endgroup\$
0
5
\$\begingroup\$

Haskell, 94 bytes

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. 
\$\endgroup\$
1
  • \$\begingroup\$ powerslice is such a great function name. \$\endgroup\$
    – Zgarb
    Jan 11, 2017 at 7:21
4
\$\begingroup\$

J, 36 35 bytes

#\*/@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

Try it online here.

\$\endgroup\$
1
  • \$\begingroup\$ I think you can save 2 bytes using the base 1 trick for summation and using a composed flatten #\*/@e.&,]({:*0=1#.{.)@|:\.\@,.#\ \$\endgroup\$
    – miles
    Jan 13, 2017 at 4:02
4
+100
\$\begingroup\$

APL (Dyalog Unicode), 22 20 bytes

-2 bytes thanks to Bubbler

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

Try it online!

Explanation

                 ,\⎕      ⍝ 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?
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Please don't use Dyalog Classic unless you really have to. \$\endgroup\$
    – Adám
    Sep 15, 2020 at 6:19
  • \$\begingroup\$ @Adám Yeah, I've read through the reasons not to and I'm using Unicode for future answers. \$\endgroup\$
    – Jo King
    Sep 15, 2020 at 6:51
  • 2
    \$\begingroup\$ A full program saves 2 bytes. \$\endgroup\$
    – Bubbler
    Sep 15, 2020 at 8:12
3
\$\begingroup\$

Ruby, 81 bytes

Try it online

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}}}}
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 109 bytes

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)

Test snippet

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>

\$\endgroup\$
2
\$\begingroup\$

Python, 123 120 bytes

-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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I think you can use 0 as the placeholder instead of None. There won't be false positives, because every 0 in the input is always part or a zero-sum slice. \$\endgroup\$
    – Zgarb
    Jan 11, 2017 at 7:23
  • \$\begingroup\$ You are right. I thought about that but ended up concluding that it could incur in false positives. \$\endgroup\$
    – dfernan
    Jan 11, 2017 at 9:05
2
\$\begingroup\$

APL (Dyalog Unicode), 22 bytes

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

Try it online!

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

How it works

≢={≢∪∊↓∘⍳/¨⍸∘.=⍨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?
\$\endgroup\$
1
\$\begingroup\$

Scala, 49 bytes

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

Try it at ideone

Usage:

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

Ungolfed:

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

Explanation:

% =>            //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
  )
\$\endgroup\$
8
  • \$\begingroup\$ I'm not exactly sure how this works, but I think it should fail on some of the truthy test cases. \$\endgroup\$
    – Zgarb
    Jan 10, 2017 at 17:08
  • \$\begingroup\$ @Zgarb I added a link to ideone, so you can verify that it's correct. It's basically a brute-force, trying every possible slice. \$\endgroup\$
    – corvus_192
    Jan 10, 2017 at 17:33
  • \$\begingroup\$ You can use % as a parameter name? Cool! \$\endgroup\$
    – Cyoce
    Jan 10, 2017 at 18:54
  • \$\begingroup\$ @Cyoce You can use pretty much any Unicode char except .,;:()[]{}\"'. Pretty useful for golfing, because they get seperated from letters by the parse, so you can save some whitespace. \$\endgroup\$
    – corvus_192
    Jan 10, 2017 at 19:52
  • \$\begingroup\$ I checked the test cases, and it seems to give true for the second falsy case. \$\endgroup\$
    – Zgarb
    Jan 10, 2017 at 20:03
1
\$\begingroup\$

Clojure, 109 bytes

#(=(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.

\$\endgroup\$
1
\$\begingroup\$

PHP, 104 bytes

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.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 102 bytes

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 1s left.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 99 bytes

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)

Try it online!

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

\$\endgroup\$
-1
\$\begingroup\$

Python, 86 Bytes

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

\$\endgroup\$
2
  • \$\begingroup\$ This incorrectly returns 1 for the third test case. \$\endgroup\$
    – Zgarb
    Jan 11, 2017 at 8:44
  • 2
    \$\begingroup\$ It actually returns 1 for all test cases except the first two falsy ones. \$\endgroup\$
    – dfernan
    Jan 11, 2017 at 9:17

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .