priyanka_1998's blog

By priyanka_1998, history, 7 years ago, In English

Problem link : https://www.codechef.com/LTIME58B/problems/ARRP Solution link : https://www.codechef.com/viewsolution/18034419

int main(){

ll t;
cin>>t;

while(t--){

    ll n;
    cin>>n;

    ll a[n];

    for(ll i=1;i<=n;i++)
       cin>>a[i];

    ll prefix[n];


    prefix[1]=a[1];

    for(ll i=2;i<=n;i++)
       prefix[i]=prefix[i-1]+a[i];

    ll sum=prefix[n];



    cout<<"1";

    for(ll i=2;i<=n;i++){

       ll flag=0;

       if(sum%i==0){

         flag=1;

         ll k=sum/i;
         ll p=k;

         for(ll j=1;j<=n;j++){

          if(prefix[j]==p)
              p=p+k;
          else if(prefix[j]>p){
              flag=0;
              break;
          }

         }          
       }

       if(flag)
         cout<<"1";
       else
         cout<<"0";

    }

    cout<<"\n";



}


return 0;

}

can anyone help me to compute the time complexity of my code . It got accepted How??

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Auto comment: topic has been updated by priyanka_1998 (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Author of this problem has analyzed about time complexity in depth about this problem here.

Also, you don't need to post the code, you can link it up to Ideone for clarity!