spider68

Longest subarray with sum divisible by K

May 31st, 2020
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     int i,j,t,n,k,y;
  6.     cin>>t;
  7.     while(t--)
  8.     {
  9.         cin>>n>>k;
  10.         int a[n],s=0;
  11.         for(i=0;i<n;i++)cin>>a[i];
  12.         int mp[k];
  13.         memset(mp,-1,sizeof(mp));
  14.         int ans=0;
  15.         for(i=0;i<n;i++)
  16.         {
  17.             s+=a[i];
  18.             y=(s%k+k)%k;
  19.             if(mp[y]==-1)mp[y]=i;
  20.             if(y==0)ans=i+1;
  21.             else ans=max(ans,i-mp[y]);
  22.         }
  23.         cout<<ans<<endl;
  24.     }
  25.     return 0;
  26. }
Add Comment
Please, Sign In to add comment