Find the subarray with the least average

Introduction

Given a whole number exhibit and size of the subarray, find the first subarray with least average in a single circle. Print first record of subarray and ordinary. The issue is I can't utilize variable substring length c without using any extra process. We want to set aggregate to 0 beyond your for circle and save a running all out for aggregate. Each cycle takes away the principal component of the past sub-exhibit while adding the new last element of the new sub-cluster. We shouldn't begin deducting till you arrive at your subsequent sub-cluster or checking for midpoints until 'I' is the previous record of the main sub-exhibit.

Also see, Array Implementation of Queue and  Rabin Karp Algorithm

Find the subarray with the least average.

We were given a cluster arr[] of size n and whole number k to such an extent that k <= n.

A Simple Solution is to consider each component as the start of the subarray of size k and register the amount of the subarray beginning with this component. The time intricacy of this arrangement is O(nk).

An Efficient Solution is to take care of the above issue in O(n) time and O(1) additional room. The thought is to utilize a sliding window of size k. Monitor the number of current k components. To register the amount of the current window, eliminate the first component of the past window and add the current component (last component of the current window).

Working

We have a variety of numbers and a number k. Our undertaking is to figure out the base average among every one of the conceivable sub-varieties of size k. We have the condition in there on the off chance that n is not precisely k. It implies assuming we pass the size of sub-varieties that we want to view as the base standard. If that exhibit is more prominent than the size of the entire cluster, then it is absurd to expect to find that sub-cluster normal in the wake of setting up the worth of aggregate and begin to 0. We will navigate the exhibit and for the main crossing till the value of k. We will get every show component, accumulate it into the total, and then update it. Some worth will be in full after the total crossing, and that is the amount of the multitude of values present in a sub-exhibit.

We will duplicate the worth of aggregate to the least sum because we will track down the base average among all the sub-exhibit of size k. We will initially cross the exhibit from the start until the first k components and store the aggregate in the least sum. A short time later, we will add arr[i] - arr[i-k] to the least sum for every I. This is simply because we have two qualities. Now we are searching for third and checking for least. Then, at that point, what we will check for is on the off chance that the least sum is not exactly k. If valid, we will refresh the worth of the least sum and the value of start to I-k+1. This condition of updation is that to keep the result as the ordering of an exhibit typical because we began with the k, we should change it.

After the crossing, we have the worth of starting, yet we don't have the closure worth of sub-cluster which has least expected; we will just put the start+k-1; this will assist in figuring out the consummation with the ordering of the sub-exhibit.

Steps

• Initialize res_index = 0//Beginning of result record
• Find the number of first k components. Allow this aggregate to be 'curr_sum.'
• Initialize min_sum = total
• Iterate from (k+1)'th to n'th component, do following

   for each component arr[i]

      a) curr_sum = curr_sum + arr[i] - arr[i-k]

      b) If curr_sum < min_sum

           res_index = (I-k+1)

• Print res_index and res_index+k-1 as starting and finishing records of the resultant subarray.

Python Code

# Python3 program to find
# minimum average subarray

# Prints beginning and ending
# indexes of subarray of size k
# with minimum average
def findMinAvgSubarray(arr, n, k):

    # k must be smaller than or equal to n
    if (n < k): return 0

    # Initialize beginning index of result
    res_index = 0

    # Compute sum of first subarray of size k
    curr_sum = 0
    for i in range(k):
        curr_sum += arr[i]

    # Initialize minimum sum as current sum
    min_sum = curr_sum

    # Traverse from (k + 1)'th
    # element to n'th element
    for i in range(k, n):
   
        # Add current item and remove first
        # item of previous subarray
        curr_sum += arr[i] - arr[i-k]

        # Update result if needed
        if (curr_sum < min_sum):
       
            min_sum = curr_sum
            res_index = (i - k + 1)
       
    print("Subarray between [", res_index,
        ", ", (res_index + k - 1),
        "] has minimum average")

# Driver Code
arr = [3, 7, 90, 20, 10, 50, 40]
k = 3 # Subarray size
n = len(arr)
findMinAvgSubarray(arr, n, k)

You can also try this code with Online Python Compiler

Run Code

Output

Subarray between [3, 5] has minimum average

The time complexity for the given code is O(n), and the auxiliary space complexity is O(1)

Check out this problem - Subarray With 0 Sum