Find max subarray divisible by K

README.md

Logic:

Already going to assume that you know about prefix sums before you read this. We can all agree that for an array A = [], where N = A.length, that there are N prefix sums.

prefix[0] = A[0], prefix[1] = A[0] + A[1], ... prefix[i] = prefix[0] + ... + prefix[i].

Then to calculate how many subarrays are divisible by K is logically equivalent to saying, how many ways can we pair up all prefix sum pairs (i,j) where i < j such that (prefix[j] - prefix[i]) % K == 0

Just from that information alone we easily get a O(n^2) solution. Compute all prefix sums, then check all pair to see if k divides the difference between them.

However, if we just exploit some information w.r.t to the remainder of each prefix sum we can manipulate this into a linear algorithm. Here's how.

Number Theory Part

Noted above that we need to find all prefix sum pairs (i,j) such that (p[j] - p[i]) % K == 0. But this is only true, if and only if p[j] % K == p[i] % K

Why is this?

According the the division algorithm we can express p[j] and p[i] in the following way. p[j] = bK + r0 where 0 <= r0 < K p[i] = aK + r1 where 0<= r1 < K

Then p[j] - p[i] = (b*K + r0) - (a*K + r1) = b*K - a*K + r0 - r1 = K*(b-a) + r0 - r1 Again: p[j] - p[i] = K*(b-a) + (r0-r1), in other words K only divides p[j] - p[i] iff r0-r1 = 0 <-> r0 = r1 QED

But we should not forget about elements in the array that do not need a pairing, namely those that are are divisible by K. That's why we add mod[0] at the end.

Also counting pairs => N choose 2 = > n*(n-1) / 2

References: Problem Solution Explained in Java

solution.js

/*
Repl.it: https://repl.it/@josgraha/max-subarray-div-by-k
*/

const range = n => [...Array(n).keys()];

// const A = [4,5,0,-2,-3,1];
// const K = 5;
const A = [-1, 2, 9];
const K = 2;

const findMaxSubarrayDivByK = (list, k) => {
  const n = list.length;
  const modGroups = range(k).map(()=>0);
  let sum = 0;
  for (let i = 0; i < n; i++) {
    sum += list[i];
    let group = sum % k;
    // handle negative modulus
    if (group < 0) {
      group += k;
    }
    const modGroupsVal = modGroups[group];
    modGroups[group] = modGroupsVal + 1;
  }
  let total = 0;
  modGroups.forEach(x => {
    if( x > 1) {
      total += (x*(x-1)) / 2;
    }
  });
  // don't forget all numbers that divide K
  return total + modGroups[0];
}

// expected 7
console.log(findMaxSubarrayDivByK(A, K));