CODEWITHSUNDEEP
python
jojo33
jojo33

Reputation: 55

Trying to find the smallest sums comprised of n contiguous values in an array

ar = [15,10,20,5,7,9,35,77]

def smallestSubArraySizeN(array, n):
    current_smallest = 9000
    unf = 0
    sum = 0
    for i in range(len(array)-n):

        while unf < n:
            sum += array[i+unf]
            unf += 1
        if sum < current_smallest:
            current_smallest = sum
        else:
            sum = sum-array[i]
        unf = 0
    print("thisis" , current_smallest)
    return current_smallest


a = smallestSubArraySizeN(ar,3)

So here I would expect to get 5+7+9 = 21 but when I run this I am getting 45. I am wondering where my logic fails, if anyone has any ideas, thanks a lot!

Upvotes: 0

Views: 55

Answers (3)

Kelly Bundy
Kelly Bundy

Reputation: 27588

  • Always remove the first value from the sum.
  • When you do, decrease unf by 1, don't set it to 0.
  • Add +1 to the range so you don't miss the last value/sum.
ar = [15,10,20,5,7,9,35,77]

def smallestSubArraySizeN(array, n):
    current_smallest = 9000
    unf = 0
    sum = 0
    for i in range(len(array)-n+1):

        while unf < n:
            sum += array[i+unf]
            unf += 1
        if sum < current_smallest:
            current_smallest = sum
        sum = sum-array[i]
        unf -= 1
    print("thisis" , current_smallest)
    return current_smallest


a = smallestSubArraySizeN(ar,3)

Upvotes: 1

Chris
Chris

Reputation: 36451

It seems like you're doing a lot of work. Rather you can use a generator expression to create a sequence of list slices to sum, and then find the min of those sums.

def smallest_sum(lst, n):
    return min(sum(lst[i:i+n]) for i in range(len(lst) - n + 1))

Upvotes: 1

BrokenBenchmark
BrokenBenchmark

Reputation: 19223

This approach seems a little too complex. You can use a sliding window instead.

You shouldn't use sum() inside a generator comprehension; it's not worth the extra conciseness. You'll recompute the sum over (roughly) the same numbers over and over again, meaning that the complexity can be quadratic in the size of the array in the worst case. This will always run in linear time, as it's a one pass algorithm:

from math import inf
def smallestSubArraySizeN(array, n):
    smallest_total = current_total =  sum(array[:n])
    for idx in range(n, len(array)):
        current_total += array[idx] - array[idx - n]
        smallest_total = min(current_total, smallest_total)
    
    return smallest_total

For the given input, this outputs:

21

Upvotes: 0

Related Questions