Subarray with Sum Divisible by Length of Array (Java)

From LiteratePrograms

Here we are going to demonstrate a simple fun result from number theory. Given a non-empty array of integers, we are going to compute a non-empty sub-array (i.e. a contiguous range of indexes) such that the sum of the integers in the sub-array is divisible by the length of the original array (and argue that such a subarray must exist). (Denote the length of the original array by n.) Furthermore, we will do this in linear time.

<<compute subarray>>=
public static void computeSubarray(int[] a) {
    compute partial sums
    fill in remainders
}

Computing Partial Sums

First, we are going to construct another array b, whose element b[i] is the sum of all the elements in the original array from the beginning up to (but not including) i, modulo n. So b]0] = 0, b[1] = a[0] % n, b[2] = (a[0] + a[1]) % n, and so on, until b[n] = (a[0] + ... + a[n-1]) % n.

Recall that a number is divisible by n if its remainder when divided by n is 0; and that remainders are preserved through addition, so that (a + b) % n = (a % n + b % n) % n.

<<compute partial sums>>=
int[] b = new int[a.length + 1];
b[0] = 0;
for (int i = 0; i < a.length; i++)
    b[i+1] = (b[i] + a[i]) % a.length;

This is useful because any subarray is just the difference between two subarrays that start at the beginning. For example, the subarray consisting of the 4th and 5th elements is the difference between the subarray of the first 5 elements and the one of the first 3 elements. So the sum of any subarray (modulo n) is the difference between the corresponding b[i]'s. The subarray we are looking for has a difference between corresponding b[i]'s of 0; i.e. we are looking for two b[i]'s that are the same.

Technically, we don't need to store this array at all. We could just keep track of one value at a time and directly compute the next part as we traverse through the a array. But for clarity we will do this in steps.

Fill in Table of Remainders

Now we create another array. The i'th position in the array will correspond to the index in the b array whose value is i. There are only n possible values for elements in b (there are only n remainders when divided by n), from 0 to n-1.

We begin by filling it with -1:

<<fill in remainders>>=
int[] c = new int[a.length];
Arrays.fill(c, -1);

Now we will iterate through b and figure out what position to put it. We then check the existing value at that location in c. If the value is -1, that means we have not filled it yet, and we will replace it with the new value. However, if the existing value is not -1, then we have filled it before, meaning that there has already been another b[i] whose value is equal to the current one. If this happens we have found what we are looking for

<<fill in remainders>>=
for (int i = 0; i < b.length; i++) {
    int pos = b[i];
    if (c[pos] < 0)
        c[pos] = i;
    else {
        found solution
    }
}

Now comes the important question, what happens if the for-loop ends, and we have not found a solution? We will present a counting argument that this is impossible. Notice that the array b has n + 1 elements, while the array c has only n elements. Therefore, if the loop ends, then n + 1 distinct elements in c must have been filled. (They have to be distinct because if we tried to fill the same element twice, then we found a solution.) But c doesn't have that many elements. Contradiction.

<<fill in remainders>>=
// you are not supposed to get here
System.err.println("You broke math.");
System.exit(1);

When we find a solution, we print out information about it:

<<found solution>>=
int begin = c[pos], end = i;
int sum = 0;
for (int j = begin; j < end; j++)
    sum += a[j];
System.out.println("found solution: subarray from index " + begin + " (inclusive) to " + end + " (exclusive)");
System.out.println("has sum = " + sum + ", which is divisible by length of array " + a.length);
return;

Conclusion

The running time of the algorithm is linear time, because we only traverse through a once, and we traverse through part of b once (and we optionally traverse through part of a again to compute the sum of the subarray once we found it).

Finally, we put it together in a class and add a main function:

<<SubarraySumDivisible.java>>=
import java.util.Arrays;
public class SubarraySumDivisible
{
    compute subarray
    public static void main(String[] args) {
        // TODO: parse this from the user or generate randomly
        int[] a = {63, 92, 51, 92, 39, 15, 43, 89, 36, 69, 40, 16, 23, 2, 29, 91, 57, 43, 55, 22};
        computeSubarray(a);
    }
}

Download code