1
\$\begingroup\$

I need to find the largest interval with a value less than a limit Lt.

The data is as follows:

For every test case T:

  • Number of elements N, limit Lt
  • N number of elements data

I wrote the following algorithm:

  • Create a CF Table while taking input
  • While size of interval plus current_Pos < number of elements, increase the size of interval while interval value less than limit, else increase the current_Pos

#include <iostream>
typedef long long int ll;
using namespace std;
ll a[1000000+100]={0};
int main() {
    // your code goes here
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,lt;
        cin>>n>>lt;
        for(ll i=0;i<n;i++)
            cin>>a[i],a[i]+=a[i-1];
        ll i=0,size=0,ans=0;
        while(i+size<n)
        {
            while(a[i+size]-a[i-1]<=lt && i+size<n){ans=a[i+size]-a[i-1];size++;
            }
            i++;
        }
        cout<<ans<<" "<<size<<endl;
    }
    return 0;
}

While a similar strategy here which increases the interval and shifts it by adding the next element and removing the previous one works:

#include <iostream>
#include <cstdio>
using namespace std;
int a[100006];
int main()
{
    int s,p,q,ans1,ans2,i,j,n,m,k,t,b,c,d;
    scanf("%d",&t);
    for(k=1;k<=t;k++)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        ans1=100000000;
        ans2=0;
        p=1;
        q=1;
        s=a[1];
        while(q<=n && p<n)
        {
            if(s<=m)
            {
                if(q-p+1>ans2)
                {
                    ans2=q-p+1;
                    ans1=s;
                }
                else
                    if(q-p+1==ans2)
                        ans1=min(ans1,s);
            }
            if(s<m)
            {
                q++;
                s=s+a[q];
            }
            else
            {
                p++;
                s=s-a[p-1];
            }
        }
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}

I'd like to know where my approach fails and its actual running time.

\$\endgroup\$
  • \$\begingroup\$ You're asking "where my approach fails", do you mean fails a code review and could be improved or are you not getting the results you intend? \$\endgroup\$ – SuperBiasedMan Nov 13 '15 at 14:10
  • \$\begingroup\$ Fails here means failing to being bounded under O(N) ... \$\endgroup\$ – Siddharth Singh Nov 13 '15 at 14:11
  • \$\begingroup\$ I am getting the desired results but it seems to exceed the time limit even though it is clearly O(N) , i don't know what am I missing in my analysis \$\endgroup\$ – Siddharth Singh Nov 13 '15 at 14:12
  • \$\begingroup\$ Has there been a limit on time to comment the code, too? Consider using variable names with more than one letter. \$\endgroup\$ – greybeard Jan 13 '16 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.