4
\$\begingroup\$

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

1 Answer 1

6
\$\begingroup\$
  1. 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.

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

  3. 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)))
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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