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

edited Nov 19 '18 at 20:15

eozd

8941515

asked Nov 19 '18 at 18:19

Thegreatfoo

385

Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52

Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05

You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07

*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13

add a comment |

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

edited Nov 19 '18 at 20:15

eozd

8941515

asked Nov 19 '18 at 18:19

Thegreatfoo

385

Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52

Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05

You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07

*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13

add a comment |

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

edited Nov 19 '18 at 20:15

eozd

8941515

asked Nov 19 '18 at 18:19

Thegreatfoo

385

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

python python-3.x

edited Nov 19 '18 at 20:15

eozd

8941515

asked Nov 19 '18 at 18:19

Thegreatfoo

385

edited Nov 19 '18 at 20:15

eozd

8941515

asked Nov 19 '18 at 18:19

Thegreatfoo

385

edited Nov 19 '18 at 20:15

eozd

8941515

edited Nov 19 '18 at 20:15

eozd

8941515

edited Nov 19 '18 at 20:15

eozd

8941515

asked Nov 19 '18 at 18:19

Thegreatfoo

385

asked Nov 19 '18 at 18:19

Thegreatfoo

385

asked Nov 19 '18 at 18:19

Thegreatfoo

385

Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52

Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05

You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07

*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13

add a comment |

Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52

Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05

You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07

*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13

Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52

Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05

You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07

*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13

add a comment |

2 Answers
2

active

oldest

votes

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)]

answered Nov 19 '18 at 19:06

blhsing

28.7k41336

If max length is N-1, the OP may need it to generalize to any N
– Brian Cohan
Nov 19 '18 at 19:16

1

Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29

add a comment |

You can split your problem into two subproblems:

The elements in your list sum up to N. Then you can simply test:
```
if sum(myList) == N:

    # do fancy stuff
```

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.

edited Nov 19 '18 at 19:07

answered Nov 19 '18 at 18:58

Neb

1,246517

The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05

You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53380515%2fhow-to-check-if-sum-of-some-contiguous-subarray-is-equal-to-n%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

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)]

answered Nov 19 '18 at 19:06

blhsing

28.7k41336

If max length is N-1, the OP may need it to generalize to any N
– Brian Cohan
Nov 19 '18 at 19:16

1

Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29

add a comment |

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)]

answered Nov 19 '18 at 19:06

blhsing

28.7k41336

If max length is N-1, the OP may need it to generalize to any N
– Brian Cohan
Nov 19 '18 at 19:16

1

Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29

add a comment |

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)]

answered Nov 19 '18 at 19:06

blhsing

28.7k41336

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)]

answered Nov 19 '18 at 19:06

blhsing

28.7k41336

answered Nov 19 '18 at 19:06

blhsing

28.7k41336

answered Nov 19 '18 at 19:06

blhsing

28.7k41336

answered Nov 19 '18 at 19:06

blhsing

28.7k41336

If max length is N-1, the OP may need it to generalize to any N
– Brian Cohan
Nov 19 '18 at 19:16

1

Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29

add a comment |

If max length is N-1, the OP may need it to generalize to any N
– Brian Cohan
Nov 19 '18 at 19:16

1

Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29

If max length is N-1, the OP may need it to generalize to any N
– Brian Cohan
Nov 19 '18 at 19:16

Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29

add a comment |

You can split your problem into two subproblems:

The elements in your list sum up to N. Then you can simply test:
```
if sum(myList) == N:

    # do fancy stuff
```

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.

edited Nov 19 '18 at 19:07

answered Nov 19 '18 at 18:58

Neb

1,246517

The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05

You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06

add a comment |

You can split your problem into two subproblems:

The elements in your list sum up to N. Then you can simply test:
```
if sum(myList) == N:

    # do fancy stuff
```

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.

edited Nov 19 '18 at 19:07

answered Nov 19 '18 at 18:58

Neb

1,246517

The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05

You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06

add a comment |

You can split your problem into two subproblems:

The elements in your list sum up to N. Then you can simply test:
```
if sum(myList) == N:

    # do fancy stuff
```

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.

edited Nov 19 '18 at 19:07

answered Nov 19 '18 at 18:58

Neb

1,246517

You can split your problem into two subproblems:

The elements in your list sum up to N. Then you can simply test:
```
if sum(myList) == N:

    # do fancy stuff
```

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.

edited Nov 19 '18 at 19:07

answered Nov 19 '18 at 18:58

Neb

1,246517

edited Nov 19 '18 at 19:07

answered Nov 19 '18 at 18:58

Neb

1,246517

answered Nov 19 '18 at 18:58

Neb

1,246517

answered Nov 19 '18 at 18:58

Neb

1,246517

The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05

You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06

add a comment |

The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05

You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06

The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05

You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu