CODEWITHSUNDEEP
pythonpython-3.x
Thegreatfoo
Thegreatfoo

Reputation: 97

How to check if sum of some contiguous subarray is equal to N?

So say I have a list sequences such as this.

I want to remove all sequences where its total sum = N and/or it has a contiguous subarray with sum = N.

For example, if N = 4, then (1,1,2) is not valid since its total is 4. (1,1,3) is also not valid since the (1,3) is also 4. (1,3,1) is also not valid for the same reason.

lst = [ 
    (1,1,1), (1,1,2), (1,1,3), 
    (1,2,1), (1,2,2), (1,2,3), 
    (1,3,1), (1,3,2), (1,3,3), 
    (2,1,1), (2,1,2), (2,1,3), 
    (2,2,1), (2,2,2), (2,2,3), 
    (2,3,1), (2,3,2), (2,3,3), 
    (3,1,1), (3,1,2), (3,1,3), 
    (3,2,1), (3,2,2), (3,2,3), 
    (3,3,1), (3,3,2), (3,3,3) 
]

What are some ways to do this?

I'm currently trying to see if I'm able to remove sequences whose total is not necessarily a multiple of N but not its contiguous subarrays, but I'm unsuccessful

   for elements in list(product(range(1,n), repeat=n-1)):
        lst.append(elements)
    for val in lst:
        if np.cumsum(val).any() %n != 0:
            lst2.append(val) # append value to a filtered list

Upvotes: 3

Views: 226

Answers (2)

Neb
Neb

Reputation: 2280

You can split your problem into two subproblems:

  1. The elements in your list sum up to N. Then you can simply test:

    if sum(myList) == N:
    # do fancy stuff

  2. The elements in your list do not sum up to N. In this case, there might be a subsequence that sum up to N. To find it, let's define two pointers, l and r. Their name stand for left and right and will define the boundaries of your subsequence. Then, the solution is the following:

    r = 1
l = 0
while r <= len(myList):
    sum_ = sum(myList[l:r])
    if sum_ < 4:
        r += 1
    elif sum_ > 4:
        l += 1
    else:
        # do fancy stuff and exit from the loop
        break

    It works as follows. First you initialize l and r so that you consider the subsequence consisting of only the first element of myList. Then, you sum the element of the subsequence and if the sum is lower than N, you enlarge the subsequence by adding 1 to r. If it is greater than N, then you restrict the subsequence by adding 1 to l.

Note thanks to eozd:

The above algorithm works only if the elemnent of the list are non-negative.

Upvotes: 2

blhsing
blhsing

Reputation: 106553

You can use itertools.combinations to generate all combinations of slice indices to test for sums of subsequences:

from itertools import combinations
[t for t in lst if not any(sum(t[l:h+1]) == 4 for l, h in combinations(range(len(t)), 2))]

This returns:

[(1, 1, 1), (1, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 1), (3, 2, 3), (3, 3, 2), (3, 3, 3)]

Upvotes: 2

Related Questions