38
\$\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\$
  • \$\begingroup\$ By "every element belongs to one of the slices", are you treating the same value at different indices as distinct? \$\endgroup\$ – ngenisis Jan 10 '17 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 '17 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 '17 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 '17 at 21:35
  • \$\begingroup\$ Understood. That makes it harder. :o) \$\endgroup\$ – dfernan Jan 10 '17 at 21:37

13 Answers 13

11
\$\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\$
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\$
  • 1
    \$\begingroup\$ Tr[1^#] saves 1 byte from Length@#. \$\endgroup\$ – ngenisis Jan 10 '17 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 '17 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\$ – Greg Martin Jan 10 '17 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\$
4
\$\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\$
  • \$\begingroup\$ powerslice is such a great function name. \$\endgroup\$ – Zgarb Jan 11 '17 at 7:21
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\$
3
\$\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\$
  • \$\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 '17 at 4:02
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\$
1
\$\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\$
  • 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 '17 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 '17 at 9:05
0
\$\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\$
  • \$\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 '17 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 '17 at 17:33
  • \$\begingroup\$ You can use % as a parameter name? Cool! \$\endgroup\$ – Cyoce Jan 10 '17 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 '17 at 19:52
  • \$\begingroup\$ I checked the test cases, and it seems to give true for the second falsy case. \$\endgroup\$ – Zgarb Jan 10 '17 at 20:03
0
\$\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\$
  • \$\begingroup\$ This incorrectly returns 1 for the third test case. \$\endgroup\$ – Zgarb Jan 11 '17 at 8:44
  • 1
    \$\begingroup\$ It actually returns 1 for all test cases except the first two falsy ones. \$\endgroup\$ – dfernan Jan 11 '17 at 9:17
0
\$\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\$
0
\$\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\$
0
\$\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\$

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.