Longest Subarray with Sum Divisible by K | Algorithms Notes

Longest Subarray with Sum Divisible by K | Algorithms Notes
Given an integer array A of length n and an integer K, design an O(n lg n) algorithm to find the longest subarray, subject to the sum of the subarray is divisible by K.
Solution:
Let S[i] be the sum of A[1..i], R[i] be S[i] % K. The sum of subarray A[i..j] = S[j] – S[i] is divisible by K if, and only if, R[i] = R[j]. Hence, we can sort R[i] and find the largest i – j, such that R[i] = R[j]. The total complexity is O(n lg n).

We also can count the number of subarrays whose sum is divisible by K. Let Q[i] be the number of indicies with R[j] = i. The sum of (Q[i] * Q[i-1])/2 over all i is the number of subarrays whose sum is divisible by K. The total complexity is O(n lg n).

We also can find the maximum subarray sum subject to the sum of the subarray is divisible by K. For an index j, we want to find i < j, such that R[i] = R[j] with minimum sum of S[i]. This can be done by using a self-balancing binary search tree. The total complexity is O(n lg n).

http://stackoverflow.com/questions/13089010/find-longest-subarray-whose-sum-divisible-by-k

Let s[i] = sum of first i elements modulo K.

We have:

s[i] = (s[i - 1] + a[i]) % K

We have to find, for each i, the smallest j such that s[i] == s[j]. You can find this by hashing thes[i] values. If K is small, you can just keep an array p[i] = first position for which s[k] == i.

The complexity is O(n).

http://www.zrzahid.com/subarray-with-sum-divisible-by-k/

Given an array of random integers, find subarray such that sum of elements in the element is divisible by k.

               (A[i]+A[i+1]+...+A[j])%K = 0. Which is equivalent to
           <=> (A[0]+A[1]+....+A[j])%K = (A[0]+A[1]+...A[i])%K

1. So we need to find such a pair of indices (i, j) that they satisfy the above condition.
2. Find Cumulative sum and get mod K of the sum for each position
3. Now, subarray by each pair of positions with same value of cumsum mod k constitute a continuous range whose sum is divisible by K.

public static int[] SubArraySumModK(final int A[], final int K) {
    int sum = 0;
    final Map<Integer, Integer> candidates = new HashMap<Integer, Integer>();

    for (int i = 0; i < A.length; i++) {
        sum += A[i];
        if (!candidates.containsKey(sum % K)) {
            candidates.put(sum % K, i);
        } else {
            // a subarray found
            return Arrays.copyOfRange(A, candidates.get(sum % K) + 1, i+1);
        }
    }
    return null;
}

Given an array of random integers, find max length subarray such that sum of elements in the element is equal a given number.

Similar approach as above. Instead of keeping one index per cumsum (mod k) we now need to maintain a list of indices that have same cumsum. Each pair of these lists is a candidate subarray. So, keep updating the max size among subarrays. Thats is our answer.

Read full article from Longest Subarray with Sum Divisible by K | Algorithms Notes