Monk Best Friend

QUESTION

Monk and his best friend Micro were taking a stroll, when they found an array A having N integers lying on the road. The array was injured badly, so they took it with them and treated it.\nWhen the array came back to senses, it told them, that some crazy guy came and started beating it. The array started crying and while Monk and Micro were comforting it, the last element of the array informed that the special integer is missing from its pocket. After hearing that, the array started crying even louder because it is supposed to appear in the next Code Monk Challenge with that Special Integer.\nSpecial integer, K, of an array, is an integer such that none of its subarray of size K has sum of elements greater than X. To calm the array down, Monk decided to gift it the maximum possible value of special integer K. Now since Monk is busy with Code Monk he asked Micro to find the maximum value of special integer but right now, all Micro can think of is a Potato, so Micro asked for your help.\n\nInput Format: \nFirst line consists of two space separated integers denoting N and X.\nSecond line consists of N space separated integers denoting the array A.\nOutput Format:\nPrint the maximum possible value of special integer.\n\nSAMPLE INPUT \n4 8\n1 2 3 4\n\n\nSAMPLE OUTPUT \n2\n\nExplanation\nSum of all subarrays of size 1: 1,2,3,4\nSum of all subarrays of size 2: 3,5,7\nSum of all subarrays of size 3: 6,9\nSum of all subarrays of size 4: 10 \nSo clearly, maximum subarray size, such that all subarrays of that size have sum of elements less than 8 is 2.\n\n.

“TESTCASE_1”: “4 8\n1 2 3 4\n###—###SEPERATOR—###—\n2”, “TESTCASE_2”: “5 26\n2 10 9 5 1\n###—###SEPERATOR—###—\n4”, “TESTCASE_3”: “6 15\n3 5 8 10 1 6\n###—###SEPERATOR—###—\n1”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <stdio.h>
int main()
{
    long long int n,x,k,i,j;
    scanf("%lld %lld",&n,&x);
    long long int a[n];
    k=n;
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        if(i>0)
        a[i]+=a[i-1];
    }
    j=0;
    while(a[j]<=x && j<n)
    j++;
    if(j<k && j!=n)
    k=j;
    j--;
    for(i=1;i<n;i++)
    {
        while(a[j]-a[i-1]<=x && j<n)
        j++;
        if(j-i<k && j!=n)
        k=j-i;
        j--;
    }
    printf("%lld",k);
    return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.