Number of subarrays divisible by k

Question

I had the following question in an interview and, in spite of the fact that I gave a working implementation, it wasn't efficient enough.

A slice of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. A slice (P, Q) of array A is divisible by K if the number A[P] + A[P+1] + ... + A[Q−1] + A[Q] is divisible by K.

The function I was asked to write, had to return the number of slices divisible by K. The expected time complexity was O(max(N, K)) and space complexity was O(K).

My solution was the simplest, one loop inside another and check every slice: O(n^2)

I have been thinking but I really can't figure out how can I do it in O(max(N, K)).

It may be a variant of the subset sum problem, but I don't know how to count every subarray.

EDIT: Elements in array could be negatives. Here is an example:

A = {4, 5, 0, -2, -3, 1}, K = 5

Function must return 7, because there are 7 subarrays which sums are divisible by 5
{4, 5, 0, -2, -3, 1}
{5}
{5, 0}
{5, 0, -2, -3}
{0}
{0, -2, -3}
{-2, -3}

Aerography

Answer 1

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 = 0
for i = 0 to N - 1
  s = ( s + A[i] ) % K
  B[s]++
ans = 0
for 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 ).

Annulose

sorry, I forgot to say that elements in array could be negatives – Aerography

It doesn't change anything, my solution is still valid. – Annulose

Thank you very much for your answer, but I don't know if I don't get it of it just doesn't work. I prove with for example array {1, 2, 3} and k = 3 and the result is 1, when it should be 3. Could you explain a little bit more your answer? – Aerography

Indeed the last line ans += B[i]*(B[i]+1)/2 counts only splices of size > 1, I have modified it. – Annulose

It doesn't work with k = 6 and A = {1, 2, 3}. It returns 3, and it should be one. Maybe it's a little mistake, but I can't fix it because I still don't understand your reasoning. Why do you multiply B[i] * (B[i]+1) ? – Aerography

Indeed, I fixed it the wrong way. I add more explanations in the answer. – Annulose

Great! Now I understand your approach. My mistake was that I was working with negative modulo. Thank very much for your time – Aerography

what does B[0]++ and B[S]++ means? – Cerise

@Annulose This doesn't work if the cumulative sum ever becomes negative (which can happen if you have large negative numbers mod K due to the way some languages handle modulus). The fix is to make sure your modulus result is always in the range [0, k). The simplest way to do that is: s = (((s + A[i]) % K) + K) % K – Gautea

@JohnKurlak My code is just pseudocode, it has to be translated to another programming language if you want to execute it. The problem you describe is a translation problem, not a problem of my code. – Annulose

@Annulose From a theoretical standpoint, modulo is defined only for positive numbers. For negative numbers, modulo doesn't have a defined value. If you claim that your solution works for negative numbers, you should define how modulo works for negative numbers. – Gautea

Let: A[]={1,2,3} and K=5. then S[]=[1,3,1] and A[2..3] (2,3) is a subarray divisible by K. then the statement that (P, Q) is a slice divisible by K if S[P] = S[Q] should be: (P, Q) is a slice divisible by K if S[P-1]=S[Q]. since S[2] is not equal to S[3] but S[1] is equal to S[3]. – Ruano

What is B[0]++ for? – Natividadnativism

ans = ans + B[i] * ( B[i] - 1 ) / 2 I want to clarify this for anybody else that didn't understand: B contains the number of sums mod K at each indexed mod. Since we're trying to find the number of differences in sum mod K = 0, the only way to achieve that is by subtracting two sums in the array that have the same mod. This line accomplishes that by finding the number of 2-combinations in each mod of B. n choose 2 = n!/(2!(n-2)!) = n(n-1)/2 – Sajovich

Answer 2

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

Jill

Answer 3

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

Neoptolemus

Answer 4

    private int GetSubArraysCount(int[] A, int K)
    {
        int N = A.Length;
        int[] B = new int[K];
        for (int i = 0; i < B.Length; i++)
        {
            B[i] = 0;
        }
        B[0]++;
        int s = 0;
        for (int i = 0; i < N; i++)
        {
            s = (s + A[i]) % K;
            while (s < 0)
            {
                s += K;
            }
            B[s]++;
        }
        int ans = 0;
        for (int i = 0; i <= K - 1; i++)
        {
            ans += B[i] * (B[i] - 1) / 2;
        }
        return ans;
    }

Flavin

Answer 5

Thanks for your solution, @damluar, it's very neat though! I just want to add some comments.

1. The output should be 7, not 6 as your output. Because we have 7 subarrays that are divisible by k as below, adding res += storedArray[0]; to fix it.

{4, 5, 0, -2, -3, 1}; {5}; {5, 0}; {5, 0, -2, -3}; {0}; {0, -2, -3}; {-2, -3}

Ref link

2. Initializing cache[0]++; depends on the language, if using C++, it's needed, but it's unnecessary for java [link].

Code:

public class HelloWorld{

public static void main(String []args){
    int [] A = new int[] {4,5,0,-2,-3,1};
    int k = 5;
    int ans=0;
    System.out.println(countSubArray(A, k)); // output = 7

}

public static int countSubArray(int [] nums, int k){
    int [] storedArray = new int[k];
    int sum=0, res=0;
    for(int i=0; i<nums.length; i++){
        sum = (((sum + nums[i]) % k) + k) % k;
        res += storedArray[sum];
        storedArray[sum]++;

    }
    res += storedArray[0];
    return res; 
}
}

Unpile

Answer 6

static void Main(string[] args)
    {
        int[] A = new int[] { 4, 5, 0, -2, -3, 1 };
        int sum = 0;
        int i, j;
        int count = 0;
        for (i = 0; i < A.Length; i++)
        {
            for (j = 0; j < A.Length; j++)
            {
                if (j + i < 6)
                    sum += A[j + i];
                if ((sum % 5) == 0)
                    count++;

            }
            sum = 0;
        }
        Console.WriteLine(count);
        Console.ReadLine();


    }

Clubwoman

Suggestion: you're iterating through the whole array in the inner loop, when you really only have to go through part of it--since j + i is going to reach 6 partway through. Also, you're using sum in a comparison right after that even though it's not been set in that iteration. This solution needs some work still. – Efthim

OP asked for an efficient approach, this is a brute force solution – Ligan

Answer 7

public class SubArrayDivisible 
{

    public static void main(String[] args) 
    {
        int[] A = {4, 5, 0, -2, -3, 1};
        SubArrayDivisible obj = new SubArrayDivisible();
        obj.getSubArrays(A,5);
    }

    private void getSubArrays(int[] A,int K)
    {
        int count = 0,s=0;
        for(int i=0;i<A.length;i++)
        {
            s = 0;
            for(int j = i;j<A.length;j++)
            {
                s = s+A[j];
                if((s%K) == 0)
                {
                    System.out.println("Value of S "+s);
                    count++;
                }

            }
        }
        System.out.println("Num of Sub-Array "+count);
    }
}

Southerner

That's the solution I gave in the interview, but its complexity is O(n!) and they asked for O(max(k,n)). Thomas' solution is the correct one – Aerography