Pythonic way of checking if indefinite # of consec elements in list sum to given value

Question

Having trouble figuring out a nice way to get this task done.

Say i have a list of triangular numbers up to 1000 -> [0,1,3,6,10,15,..]etc

Given a number, I want to return the consecutive elements in that list that sum to that number.

i.e.

64 --> [15,21,28]
225 --> [105,120]
371 --> [36, 45, 55, 66, 78, 91]

if there's no consecutive numbers that add up to it, return an empty list.

882 --> [ ] 

Note that the length of consecutive elements can be any number - 3,2,6 in the examples above.

The brute force way would iteratively check every possible consecutive pairing possibility for each element. (start at 0, look at the sum of [0,1], look at the sum of [0,1,3], etc until the sum is greater than the target number). But that's probably O(n*2) or maybe worse. Any way to do it better?

UPDATE: Ok, so a friend of mine figured out a solution that works at O(n) (I think) and is pretty intuitively easy to follow. This might be similar (or the same) to Gabriel's answer, but it was just difficult for me to follow and I like that this solution is understandable even from a basic perspective. this is an interesting question, so I'll share her answer:

def findConsec(input1 = 7735):

    list1 = range(1, 1001)
    newlist = [reduce(lambda x,y: x+y,list1[0:i]) for i in list1]

    curr = 0
    end = 2
    num = sum(newlist[curr:end])

    while num != input1:

        if num < input1:
            num += newlist[end]
            end += 1

        elif num > input1:
            num -= newlist[curr]
            curr += 1

        if curr == end:
            return []

    if num == input1:
        return newlist[curr:end]

Answer 1

A 3-iteration max solution Another solution would be to start from close where your number would be and walk forward from one position behind. For any number in the triangular list vec, their value can be defined by their index as:

vec[i] = sum(range(0,i+1))

The division between the looking-for sum value and the length of the group is the average of the group and, hence, lies within it, but may as well not exist in it. Therefore, you can set the starting point for finding a group of n numbers whose sum matches a value val as the integer part of the division between them. As it may not be in the list, the position would be that which minimizes their difference.

# vec as np.ndarray -> the triangular or whatever-type series
# val as int -> sum of n elements you are looking after
# n as int -> number of elements to be summed
import numpy as np

def seq_index(vec,n,val):
    index0 = np.argmin(abs(vec-(val/n)))-n/2-1 # covers odd and even n values
    intsum = 0 # sum of which to keep track
    count = 0 # counter
    seq = [] # indices of vec that sum up to val

    while count<=2: # walking forward from the initial guess of where the group begins or prior to it
        intsum = sum(vec[(index0+count):(index0+count+n)])
        if intsum == val:
            seq.append(range(index0+count,index0+count+n))
        count += 1
    return seq

# Example

vec = []

for i in range(0,100):
    vec.append(sum(range(0,i))) # build your triangular series from i = 0 (0) to i = 99 (whose sum equals 4950)

vec = np.array(vec) # convert to numpy to make it easier to query ranges

# looking for a value that belong to the interval 0-4590
indices = seq_index(vec,3,4)
# print indices
print indices[0]
print vec[indices]
print sum(vec[indices])

Returns

print indices[0] -> [1, 2, 3]
print vec[indices] -> [0 1 3]
print sum(vec[indices]) -> 4 (which we were looking for)

Answer 2

This seems like an algorithm question rather than a question on how to do it in python.

Thinking backwards I would copy the list and use it in a similar way to the Sieve of Eratosthenes. I would not consider the numbers that are greater than x. Then start from the greatest number and sum backwards. Then if I get greater than x, subtract the greatest number (exclude it from the solution) and continue to sum backward. This seems the most efficient way to me and actually is O(n) - you never go back (or forward in this backward algorithm), except when you subtract or remove the biggest element, which doesn't need accessing the list again - just a temp var.

To answer Dunes question:

Yes, there is a reason - to subtracts the next largest in case of no-solution that sums larger. Going from the first element, hit a no-solution would require access to the list again or to the temporary solution list to subtract a set of elements that sum greater than the next element to sum. You risk to increase the complexity by accessing more elements.

To improve efficiency in the cases where an eventual solution is at the beginning of the sequence you can search for the smaller and larger pair using binary search. Once a pair of 2 elements, smaller than x is found then you can sum the pair and if it sums larger than x you go left, otherwise you go right. This search has logarithmic complexity in theory. In practice complexity is not what it is in theory and you can do whatever you like :)

Answer 3

You should pick the first three elements, sum them and do and then you keep subtracting the first of the three and add the next element in the list and see if the sum add up to whatever number you want. That would be O(n).

# vec as np.ndarray

import numpy as np    

itsum = sum(list[0:2]) # the sum you want to iterate and check its value
sequence = [[] if itsum == whatever else [range(0,3)]] # indices of the list that add up to whatever (creation)
for i in range(3,len(vec)):
    itsum -= vec[i-3]
    itsum += vec[i]
    if itsum == whatever:
        sequence.append(range(i-2,i+1)) # list of sequences that add up to whatever

Answer 4

The solution you provide in the question isn't truly O(n) time complexity -- the way you compute your triangle numbers makes the computation O(n²). The list comprehension throws away the previous work that want into calculating the last triangle number. That is: tn_i = tn_i-1 + i (where tn is a triangle number). Since you also, store the triangle numbers in a list, your space complexity is not constant, but related to the size of the number you are looking for. Below is an identical algorithm, but is O(n) time complexity and O(1) space complexity (written for python 3).

# for python 2, replace things like `highest = next(high)` with `highest = high.next()`
from itertools import count, takewhile, accumulate

def find(to_find):
    # next(low) == lowest number in total
    # next(high) == highest number not in total
    low = accumulate(count(1)) # generator of triangle numbers
    high = accumulate(count(1))
    total = highest = next(high)
    # highest = highest number in the sequence that sums to total

    # definitely can't find solution if the highest number in the sum is greater than to_find
    while highest <= to_find:
        # found a solution
        if total == to_find:
            # keep taking numbers from the low iterator until we find the highest number in the sum
            return list(takewhile(lambda x: x <= highest, low))
        elif total < to_find:
            # add the next highest triangle number not in the sum
            highest = next(high)
            total += highest
        else: # if total > to_find
            # subtract the lowest triangle number in the sum
            total -= next(low)

    return []