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 (
)
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;
}