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}

score 42 · Accepted Answer · edited Jan 13 '19 at 10:01

42

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 ).

edited Jan 13 '19 at 10:01

Amit

105
1
6

answered May 17 '13 at 10:17

Thomash

6,339
1
30
50

sorry, I forgot to say that elements in array could be negatives – antoniobg May 17 '13 at 10:32
1

It doesn't change anything, my solution is still valid. – Thomash May 17 '13 at 10:34
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? – antoniobg May 17 '13 at 11:46
Indeed the last line `ans += B[i]*(B[i]+1)/2` counts only splices of size > 1, I have modified it. – Thomash May 17 '13 at 11:56
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)` ? – antoniobg May 17 '13 at 13:58
Indeed, I fixed it the wrong way. I add more explanations in the answer. – Thomash May 17 '13 at 14:06
Great! Now I understand your approach. My mistake was that I was working with negative modulo. Thank very much for your time – antoniobg May 17 '13 at 15:46
6

what does B[0]++ and B[S]++ means? – user_CC Jul 30 '13 at 11:27
1

@Thomash 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` – John Kurlak Oct 28 '14 at 18:33
@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. – Thomash Nov 02 '14 at 21:56
5

@Thomash 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. – John Kurlak Nov 03 '14 at 03:35
1

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]. – Ritesh Sep 02 '15 at 12:48
3

What is `B[0]++` for? – cold_coder Jun 17 '16 at 19:16
4

`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 – glitchyme Jan 20 '19 at 14:03

score 4 · Answer 2 · answered Sep 21 '16 at 14:57

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

M Sach · Answer 3 · 2016-12-30T00:54:05.917

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

user2444873 · Answer 4 · 2013-06-02T11:18:06.613

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

Tung Le · Answer 5 · 2017-11-04T22:56:28.803

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

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

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

score -1 · Answer 6 · answered Jun 25 '13 at 21:24

-1

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();


    }

answered Jun 25 '13 at 21:24

annya

5
1

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. – catfood Jun 25 '13 at 21:46
OP asked for an efficient approach, this is a brute force solution – prashant Jul 18 '19 at 22:21

score -3 · Answer 7 · edited Jun 02 '13 at 10:25

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

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 — antoniobg, May 17 '13 at 19:06

Number of subarrays divisible by k

7 Answers7

Linked

Related