Number of subarrays divisible by k

As you are only interested in numbers divisible by K, you can do all computations modulo K.Consider the cumulative sum array S such that S[i] = S[0] + S[1] + ... + S[i]. Then (P, Q) is a slice divisible by K iff S[P] = S[Q] (remember we do all computations modulo K). So you just have to count for each possible value of [0 ,..., K-1] how many times it appears in S.

Here is some pseudocode:

B = new array( K )B[0]++s = 0for i = 0 to N - 1  s = ( s + A[i] ) % K  B[s]++ans = 0for i = 0 to K - 1  ans = ans + B[i] * ( B[i] - 1 ) / 2

Once you know that they are x cells in S that have value i, you want to count the number of slices the start in a cell with value i and ends in a cell with value i, this number is x ( x - 1 ) / 2. To solve edge problems, we add one cell with value 0.

What does x ( x - 1 ) / 2 stands for: Let's assume our array is [4, 5, 0] and frequency of 4 as prefix sum is x, which is 3 in this case. Now we can conclude from value of x, that there are at least x-1 numbers which are either divisible by k or have mod k equals to 0. Now total possible sub arrays out of these x-1 numbers are 1 + 2 + 3 ... + ( x - 1 ) which is ( ( x - 1 ) * ( ( x - 1 ) + 1 ) / 2 . (Standard formula for summation from 1 to N where N stands for ( x - 1 ).

Here is a Java implementation of the solution proposed by @Thomash.

The second loop is not necessary, because we can directly increase the answer by the current value and then increment it.

To avoid negative array index, we also have to adjust module computation.

public static int countSubarrays(int[] nums, int k) {    int[] cache = new int[k];    cache[0]++;    int s = 0, counter = 0;    for (int i = 0; i < nums.length; i++) {        s = ((s + nums[i]) % k + k) % k;        counter += cache[s];        cache[s]++;    }    return counter;}

Example :-

Input Array

int [] nums = {4,3,1,2,1,5,2};

K is 3

Consecutive sum

4,7,8,10,11,16,18

Divide above consecutive sum array by 3

1,1,2,1,2,1,0

so we have got four 1's, Two 2's, one 0's

so total count will be (4*3)/2 + (2*1)/2 + (2*1)/2 = 8

(4*3)/2 comes from select any two 1's out of four i.e. nC2 = n(n-1)/2

Here is the program

public static long countSubArrayDivByK(int k, int[] nums) {

    Map<Integer, Integer> modulusCountMap = new HashMap<Integer, Integer>();    int [] consecSum = new int[nums.length];    consecSum[0]=nums[0];    for(int i=1;i<nums.length;i++){        consecSum[i]= consecSum[i-1] +nums[i];    }    for(int i=0;i<nums.length;i++){        consecSum[i]= consecSum[i]%k;            if(consecSum[i]==0 && modulusCountMap.get(consecSum[i])==null){                modulusCountMap.put(consecSum[i], 2);            }else{                modulusCountMap.put(consecSum[i], modulusCountMap.get(consecSum[i])==null ? 1 : modulusCountMap.get(consecSum[i])+1);            }    }    int count = 0;    for (Integer val : modulusCountMap.values()) {        count = count +  (val*(val-1))/2;    }    return count;}

Optimized version of above

static long customOptimizedCountSubArrayDivByK(int k, int[] nums) {        Map<Integer, Integer> modulusCountMap = new HashMap<Integer, Integer>();        int [] quotient = new int[nums.length];        quotient[0]=nums[0]%3;        if(quotient[0]==0){            modulusCountMap.put(quotient[0], 2);        }else{            modulusCountMap.put(quotient[0], 1);        }        for(int i=1;i<nums.length;i++){            quotient[i]= (quotient[i-1] + nums[i])%3;                if(quotient[i]==0 && modulusCountMap.get(quotient[i])==null){                    modulusCountMap.put(quotient[i], 2);                }else{                    modulusCountMap.put(quotient[i], modulusCountMap.get(quotient[i])==null ? 1 : modulusCountMap.get(quotient[i])+1);                }        }        int count = 0;        for (Integer val : modulusCountMap.values()) {            count = count +  (val*(val-1))/2;        }        return count;    }