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

Answer 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