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

Continuous sequence against target number

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

Problem

Post problem and my code written in Python 2.7. Any advice for code bugs, performance in terms of algorithm time complexity and code style are appreciated. I did PEB8 self-check in PyCharm.

BTW, a small issue in my code is, I feel this condition end_index == len(numbers) - 1 and cur_sum < target is a bit ugly, but I do not find a better way to remove it for safe boundary check purpose.

'''
Question: Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T
Example
[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20
[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8
[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7
'''

def sum_target(numbers, target):
    start_index = 0 # inclusive
    end_index = 0 # inclusive
    cur_sum = numbers[0]
    while end_index  target:
            cur_sum -= numbers[start_index]
            start_index += 1
        elif cur_sum == target:
            return True

    return False

if __name__ == "__main__":
    print sum_target([23, 5, 4, 7, 2, 11], 20)
    print sum_target([1, 3, 5, 23, 2], 8)
    print sum_target([1, 3, 5, 23, 2], 7)

Solution

In case there's no acceptable sequence, you have to go through all the elements anyway, so it can't be lower than O(n), and your code is already O(n).

The only optimization that you could add is a condition where if the current number alone is greater than the expected sum, you skip all values until the one just after the current value.

For instance, suppose you have [2, 3, 4, 25, 7, 8, 9] and you're looking for number 17. You don't want to check 2 + 3 + 4 + 25, 3 + 4 + 25, 4+25, you can skip directly to the index of 7.

Other than that I'd just remove the comments because I don't think they really add anything.

Context

StackExchange Code Review Q#152084, answer score: 3

Revisions (0)

No revisions yet.