Find numbers of subarray of an array whose sum is divided by given number

Question

I got stuck in one algorithm question. Please suggest me some efficient algorithm for the below problem.

Question is

Find numbers of subarrays whose sum is divisible by given number.

My work

I made one algorithm, whose complexity is O(N^2), here, N = size of an array.

My Code

#include<stdio.h>

using namespace std;

 main() {
    int N;
    int P;
    int T;
    int val;
    long long int count = 0;
    long long int answer = 0;
    scanf("%d", &T);
    //T = 20;

    for(int k = 1; k <= T; k++) {
        scanf("%d", &N);
        scanf("%d", &P);
        count = 0;
        answer = 0;
        for(int i = 0; i < N; i++) {
            scanf("%d", &val);
            count += val;
            workingArray[i] = count;
        }

        for(int length = 1; length <= N; length++) {
            for(int start = 0; start <= (N-length); start++) {
                if( start == 0 ) {
                    if(workingArray[start+length-1]%P == 0) answer++;
                }
                else if( (workingArray[start+length-1] - workingArray[start-1])%P == 0) answer++;
            }
        }

        printf("Case #%d\n%lld\n", k, answer);
    }
    return 0;
 }

Solution 1

For a given number X...

The basic idea: (with informal proof of correctness)

If the sum of the numbers in the range [a, b] is divisible by X, then:

(∑i=1 to a-1input[i]) % X = (∑i=1 to binput[i]) % X

In less mathematical terms:

the sum from the first element to b = the sum from the first element to a
                                    + the sum of the elements between the two

So:

the sum of the elements between the two = the sum from the first element to b
                                        - the sum from the first element to a

Then, if those sums on the right both have the same remainder when divided by X, the remainders will cancel out and sum of the elements between the two will be divisible by X. An elaboration:

C = the sum of the elements between the two
B = the sum from the first element to b
A = the sum from the first element to a

Now we can convert B to the form PX + Q and A to the form RX + S, for some integers P, Q, R and S, with 0 <= Q, S < X. Here, by definition, Q and S would be the respective remainders of B and A being divided by X.

Then we have:

C = (PX + Q) - (RX + S)
C = PX + Q - RX - S
C = PX - RX + Q - S
C = (P-R)X + Q - S

Clearly (P-R)X is divisible by X (the result is simply (P-R)). Now we just need Q - S to be divisible by X, but, since 0 <= Q, S < X, they'll need to be equal.

Example:

Let B = 13, A = 7, X = 3.

Here B % X = 1 and A % X = 1.

We can rewrite B as 4*3 + 1 and A as 2*3 + 1.

Then C = 4*3 + 1 - 2*3 - 1 = 2*3, which is divisible by 3.

High-level approach:

Construct a hash-map of key -> value, where each value represents how many ways you can start from the beginning of the array and end up at some given position which adds up to sum mod X = key (see the "Mod 3" line and the map values in the example below).

Now, based on the logic above, we know that if two subarrays starting from the beginning and ending at positions a and b respectively, both having the same sum mod X, subarray [a, b] will be divisible by X.

So each value in the hash-map represents the size of a set of possible starting and ending points which will give us a subarray divisible by X (any point can be either a starting or ending point).

The number of possible ways to choose these starting and ending points is simply
value choose 2 = value!/(2*(value-2)!) (or 0 if value is 1).

So we calculate that for each value in the hash-map and add them all up to get the number of subarrays divisible by X.

Algorithm:

Construct a hash-map which will store the cumulative sum of all the numbers thus far mod X mapped to the count of how often that remainder value appears (constructed in expected O(n)).

Increase 0's value by one - this corresponds to the start of the array.

Initialise a count to 0.

For each value in the hash-map, add value!/(2*(value-2)!) to the count.

The count is the desired value.

Running time:

Expected O(n).

Example:

Input:    0  5  3  8  2  1
X = 3

Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

Map:
  0 -> 3
  1 -> 2
  2 -> 2

Count = 3! / 2*(3-2)! = 3  +
        2! / 2*(2-2)! = 1  +
        2! / 2*(2-2)! = 1
      = 5

The subarrays will be:

0  5  3  8  2  1
-                     0                 =  0 % 3 = 0
-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0
   ----------         5 + 3 + 8 + 2     = 18 % 3 = 0
      -               3                 =  3 % 3 = 0
            ----      2 + 1             =  3 % 3 = 0

Solution 2

I may have an easier solution. in O(n) time and O(n+k) space. where n is the size of array & k is the number we are checking the divisibility with.

Consider the array as A[n] and the number is K

1. create another array SUM_TILL_NOW[n].
2. for each A[i] fill SUM_TILL_NOW [i]= SUM_TILL_NOW[i-1]+A[i] %K; (SUM_TILL_NOW[0]= A[0])
3. find two numbers which are equal in this new Array.

To do that create a new array CHECK[] of size K.

Iterate over the SUM_TILL_NOW array and check if CHECK[SUM_TILL_NOW[i]] set.

If not set it to i.

else CHECK[SUM_TILL_NOW[i]], i is the subset where the sum is divisible by K.

Below is a c++ function of the same.

#include <iostream>
#include <string.h>

using namespace std;

void printrange(int* A, int N, int K)
{
    int STN[N], C[K];
    memset(C, -1, K*sizeof(int));
    int i;
    int sum=A[0];
    STN[0]= (A[0]%K);
    for (i= 1; i< N; i++)
    {
        sum+= A[i];
        STN[i]= sum%K;
    }
    for(i=0; i< N; i++)
    {
        if(C[STN[i]] == -1)
            C[STN[i]] =i;
        else
        {
            cout<< C[STN[i]]+1 <<" "<< i;
            break;
        }
    }
}

int main()
{
    int A[]= {6, 9, 2, 1, 8, 6, 2, 5};
    printrange(A, sizeof(A)/sizeof(A[0]), 7);
    return 0;
}

Comments

[Saeed Amiri]

You just considered consecutive elements while the question just asked for a number of subarrays, which I read as a subsequence style not a substring format, e.g you didn't take 3+2+1, or 0+3+2+1, by the way I don't know whether is important to preserve the orders or not, e.g I don't know we should count 3+2+1, 6 times or just one time. (I suppose the latter case is acceptable).

[Bernhard Barker]

@SaeedAmiri "subarray" usually refers to consecutive parts of the array, e.g. the maximum subarray problem.

[Saeed Amiri]

No is not like this, e.g in your e.g problem statement very clearly stated that "contiguous subarray", while problem name is general (which should be short, so is not necessary to write all details in the name of problem). And here in the problem definition, there is no argument about contiguity. So we should suppose that is not continues.

[Bernhard Barker]

@SaeedAmiri Well, either way, OP just clarified that it's continuous elements.

[devsda]

@Dukeling I understand the way you solved this problem. But I didn't get the feel. Can you please explain, how you build this logic from the very basic step. Thanks in advance.

[devsda]

@Dukeling And yes, I am not able to understand given statement "Then, if those sums on the right both have the same remainder when divided by X, the remainders will cancel out and sum of the elements between the two will be divisible by X."

[devsda]

@Dukeling Thanks a lot. I got the feel.

[devsda]

@Dukeling Can we do a small cdiscussion on chat. I want guide from your side, how to improve logics, coding, algorithms. Its a kind request to you please start chat.

[Bernhard Barker]

@devsda Chat room.

[Renganathan V]

@Dukeling Can you please tell how you chose "2" in the final count calculation.

[Renganathan V]

@Dukeling Thanks for the edit. will this work if there some digits with value =1 in hashmap.

[Bernhard Barker]

@RenganathanV You'll just need to use 0 instead of value choose 2 if value is 1.