In this post, we are going to solve Longest Subarray Divisible By K DSA Problem from Flipkart Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.

## Longest Subarray Divisible By K DSA Problem Statement

Given an array of N, integers Find the longest subarray which is divisible by K.

Input

The first line of the integer contains two integers N, K the number of elements in the array and K (

$1\le N,K\le {10}^{5}$)

Next line contains N spaces integers the value of the array integers value may include negative value too.

Output

For each test case print the length of the longest subarray.

Example

Input

6 3 7 8 3 -3 4 2

Output

6

## Problem Solution in C++

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,k;
cin>>n>>k;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
unordered_map<int,int>m;
m[0]=-1;
int ans=0;
int cs=0;
for(int i=0;i<n;i++){
cs+=a[i];
int r=((cs%k)+k)%k;
if(m.find(r)!=m.end()){
ans=max(ans,i-m[r]);
}else{
m[r]=i;
}
}
cout<<ans;
return 0;
}
```

## Leave a Reply