I want to find the longest continuous sub array whose sum is divisible by a number 'k'.I have already done it using brute force with complexity o(n^2).But wants to do it for o(n).can anyone suggest me the efficient way to solve this problem in o(n) time.
for eg: {1 3 1 3 6}
the max length of subarray which is divisible by 3 is 2. i.e {3,6}
Also to note that the value of k here is very large around 10^6 so I can not use the prefix sum method where in modulo of each element is recorded as it is valid for small numbers only.
so kindly suggest me the efficient way to solve this problem in C.
Here is a way that can be used:
Create an array of summation-modulo k, eg.
Let the array be: {3,4,10,15,1,4,7}
and k = 5. Then, summation modulo array would look like:
{3,2,2,2,3,2,4} which is created as: {3%5, (3+4)%5, (3+4+10)%5... } and so on. Now find max index difference b/w similar numbers. Since k<=10^6, you can easily do this using array of size k.
In this case, it can be: {(4-0 = 4) ->index of 3} or {(5-1 = 4) ->index of 2}, so 4.
#include<stdio.h>
int main(){
int n,k,i,j;
scanf("%d%d",&n,&k); //size of the input array 'n' and modular 'k'
int a[n];
for(i = 0;i < n;i++)
scanf("%d",&a[i]);
//actual processing starts
//creating summation modulo array in 'a' itself
a[0] %= k;
for(i = 1;i < n;i++){
a[i] = (a[i-1] + a[i]) % k;
}
int r[2][k];
for(i = 0;i < k;i++)
r[0][i] = r[1][i] = -1; //initializing 'r' to -1
//now evaluating min and max position of any spec no.
for(i = 0;i < n;i++){
if(r[0][a[i]] == -1)
r[0][a[i]] = i;
else
r[1][a[i]] = i;
}
//evaluation of min-max indices complete
int g = 0;
//now find max diff if both values are set
for(i = 0;i < k;i++){
if(r[0][i] != -1 && r[1][i] != -1 && r[1][i] - r[0][i] > g)
g = r[1][i] - r[0][i];
}
printf("%d\n",g); //this is the required answer
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments