CODEWITHSUNDEEP
arraysalgorithmsum
Utsav Chokshi
Utsav Chokshi

Reputation: 1395

Finding minimum sum of K Sequential items in an array

Given unordered array of size n and sub-array size k, find minimum sum out of all contiguous sub-array sums.

We will have (n-(k-1)) sub-arrays

Example :

Array(n=5): 5 3 0 2 5

k = 3

Sub-arrays : 5 3 0, 3 0 2, 0 2 5

Sums : 8, 5, 7

Minimum sum : 5

My code :

sum = 0;

    for(index=0; index<K; index++){

        sum = sum + array[index];
    }

    minSum = sum;

    if(N!=K){
        for(index=1; index<=(N-H); index++){

            sum = sum - array[index-1] + array[index+K-1];

            if(sum < minSum){
                minSum = sum;
            }
        }   
    }

    cout << minSum << endl;

My Question is :

Is there any efficient code out there to do this ? As Array having 10^5 elements, it is taking so much of time.

Upvotes: 2

Views: 797

Answers (1)

Bartlomiej Lewandowski
Bartlomiej Lewandowski

Reputation: 11170

From what I can see, you first create a window which calculates the sum of the first K elements, and then moves the window to the right, by subtracting the leftmost value and adding the rightmost one.

This is the solution with the smallest complexity.

I have created a small script that demonstrates the correctness along with time taken to execute for larger inputs.

http://ideone.com/pS7Sp5

array = (5,3,0,2,5)
K = 3
N = len(array)


def findMin(array, sub_array_size):
    sum = 0;

    for index in range(K):
        sum = sum + array[index];

    minSum = sum;

    if N != K:
        for index in range(1,(N-K)+1):
            sum = sum - array[index-1] + array[index+K-1];

            if(sum < minSum):
                minSum = sum
    return minSum

print(findMin(array,3))
print(findMin([1,0]*100000,3))

Upvotes: 3

Related Questions