HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Find an array slice equaling sum

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
equalingfindarraysumslice

Problem

I would like to be reviewed on efficiency, style, and obviously if there is a bug I would like to know.

def findsum(a, n):
  ''' Find whether a consecutive array slice sums up to n '''
  for i in range(len(a)):
    j = i + 1
    while j <= len(a):
      if sum(a[i:j]) == n:
        return True
      j += 1
  return False

Solution

-
There's a bug:

>>> a = [1, 2, 3]
>>> findsum(a, 0)
False


but the result should be True because the consecutive slice a[0:0] sums to zero.

-
The docstring could be clearer. "a consecutive array slice" — of which array? Presumably the parameter a is meant, but it is best to be explicit. Similarly, "Find whether" — and then what? The docstring should say what value is returned.

-
The function has runtime \$Θ(n^3)\$. That's because sum(a[i:j]) takes an unnecessary copy of the slice, and because it sums it starting at the beginning of the slice. But if you maintained a running sum, then the runtime would come down to \$Θ(n^2)\$. That's easy to implement using itertools.accumulate and itertools.islice:

from itertools import accumulate, islice

def findsum(a, n):
    """Return True if any consecutive slice of the sequence a sums to n,
    False if none do.

    """
    return n == 0 or any(total == n
                         for i in range(len(a))
                         for total in accumulate(islice(a, i, None)))

Code Snippets

>>> a = [1, 2, 3]
>>> findsum(a, 0)
False
from itertools import accumulate, islice

def findsum(a, n):
    """Return True if any consecutive slice of the sequence a sums to n,
    False if none do.

    """
    return n == 0 or any(total == n
                         for i in range(len(a))
                         for total in accumulate(islice(a, i, None)))

Context

StackExchange Code Review Q#109481, answer score: 6

Revisions (0)

No revisions yet.