Longest Subarray Divisible By K DSA Problem Solution

Longest Subarray Divisible By K DSA Problem Solution

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 (

1N,K105)

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;

}