minimum size sub-array with sum greater than a given value(Sliding Window Technique)

 /// Its work for non-negative value

/*
if array size is 8
value = 8
and array is : 5 1 2 3 6 5 3 1

then our sub-array is : [3, 6]
because (3+6) = 9 > 8

So, Our length is 2
*/

#include<bits/stdc++.h>
using namespace std;

int minimum_length(int a[], int n, int value)
{
    int currentsum = 0, minlength = n+1;
    int start_index = 0, finish_index = 0;

    while(finish_index < n)
    {
        while(currentsum <= value && finish_index < n)
            currentsum += a[finish_index++];

        while(currentsum > value && start_index < n)
        {
            if(finish_index - start_index < minlength)
                minlength = finish_index - start_index;

            currentsum -= a[start_index++];
        }
    }

    return minlength;
}

int main()
{
    int n, value;
    cout << "Enter Array Size :: ";
    cin >> n;

    cout << "\nEnter A Value :: ";
    cin >> value;

    int a[n];

    cout << "\nEnter Array Element :: ";
    for(int i=0; i<n; i++)
        cin >> a[i];
    cout << "\n";

    int mn = minimum_length(a, n, value);

    if(mn != n+1)
        cout << "Minimum Length :: " << minimum_length(a, n, value) << "\n";
    else
        cout << "Minimum Length is not Found." << "\n";

    return 0;
}

Comments