how to find the length of the longest contiguous subarray whose sum is divisible by a given number

Question

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.

You should ask this question on the mathematics Stack exchange site. It's not really a programming problem. — user1886323, Aug 01 '15 at 17:50
Welcome to StackOverflow, have a read [here](http://stackoverflow.com/help/on-topic) before asking please. — πάντα ῥεῖ, Aug 01 '15 at 17:51

vish4071 · Accepted Answer · 2015-08-04T10:01:10.483

3

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
}

edited Aug 04 '15 at 10:01

answered Aug 01 '15 at 18:02

vish4071

5,135
4
35
65

What is the runtime complexity of this approach? – Oliver Charlesworth Aug 01 '15 at 18:07
O(n + k). You can see for yourself that I am actually doing nothing else than accessing each element once, to create this summation-modulo array. And to find max index difference b/w equal values, keep an array of size k which holds its 1st and (updated) last occurance. You can use pair [] if c++, or, array of size [k][2] for it. Traverse it once and you are done. – vish4071 Aug 01 '15 at 18:16
Makes sense. Presumably you can reduce this to O(n) by tracking the max difference as you go, too. – Oliver Charlesworth Aug 01 '15 at 18:19
@Oliver, maybe, but I kept it as simple as possible. Also, additional factor of 'k' in complexity doesn't matter much I guess, so I didn't give much thought to it. – vish4071 Aug 01 '15 at 18:23
@Shefali, Look in the example I gave and comments. I cannot be more clear, though I can give you code implementation if you want. But I'd recommend you do it yourself. – vish4071 Aug 01 '15 at 18:24
And don't go about deleting comments here. Its not fb. :/ – vish4071 Aug 01 '15 at 18:27
@vish4071 while traversing the array of size [k][2] will it not take o(n^2). – Shefali Chaudhary Aug 01 '15 at 18:27
@vish4071 sorry it got removed by mistake :p – Shefali Chaudhary Aug 01 '15 at 18:28
Yes, you are right. It makes a difference if k>n. ;) – vish4071 Aug 01 '15 at 18:29
No. You can traverse array of [k][2] in just one loop, as in: for i from 0 to k, find d = a[i][1]-a[i][0] (if a[i][1] is set) and check if m – vish4071 Aug 01 '15 at 18:32
And @Shefali, remember to upvote and accept any answer that solves your problem on StackOverflow because unaccepted answers linger and waste others' time who try and answer them. – vish4071 Aug 01 '15 at 18:34
@vish4071 all right.I ll try and code by myself first and will ask you further doubts then :).thanks for the approach. – Shefali Chaudhary Aug 01 '15 at 18:35
@vish4071 could you please tell me how to find max index difference b/w similar numbers using single loop? as in how to store the first and last occurence of any number? – Shefali Chaudhary Aug 03 '15 at 15:42
@shefali, see the edited post. I have attached the code. – vish4071 Aug 04 '15 at 09:58
@vish4071 and how do we keep the record if k>n? – Shefali Chaudhary Aug 04 '15 at 17:26
@shefali, the above code takes care of all cases as such. – vish4071 Aug 05 '15 at 05:58
@vish4071 simple and nice algorithm :) – instance Aug 12 '15 at 13:13

how to find the length of the longest contiguous subarray whose sum is divisible by a given number

1 Answers1

Linked