CODEWITHSUNDEEP
arraysalgorithmrangemin
movinmountains
movinmountains

Reputation: 1

Least Continuous Sum of an Array given a Range

Im having trouble writing this algorithm, but i think i have a good grasp of it but keep failing. The algorithm is supposed to return the least continuous sum of an array given a range. For example, let's say the array is as such: [1, 3, 4, 2, -1, 5, -1, 1]. The function receives a range. For this example, let's say the range is 3. The goal is to find the 3 consecutive elements that have the least sum. In the example above, it would be 3. Since -1 + 5 + -1 is the 3 consecutive elements that give the smallest sum.

Pseudocode of algorithm:

def least_sum_search(length,dictionary):
least_sum = 0
max_range = 283
for i in dictionary:
    sum = 0
    look_ahead = length
    index = i
    if i + length > max_range:
        break
    while(look_ahead > 0):
        sum += dictionary[index]['price']
        index += 1
        look_ahead -= 1
    if(least_sum > sum):
        least_sum = sum
return least_sum

How would yall write this algorithm? I personally think im overthinking it. Thanks for reading!

Upvotes: 0

Views: 34

Answers (1)

aeternalis1
aeternalis1

Reputation: 675

Say you have a range of K. You can keep a sliding window of K elements and iterate through the array, adding the i'th and removing the i-K'th element at each iteration, and keep a running minimum. As follows:

def get_min_range(N,K,arr):
    running_sum = sum(arr[:K])
    ans = running_sum
    for i in range(K,N):
        running_sum += arr[i]
        running_sum -= arr[i-K]
        ans = min(running_sum, ans)
    return ans

print get_min_range(5,3,[1,2,3,4,5])

This ignores the edge case where K > N but you can handle that however you want.

Upvotes: 2

Related Questions