josgraha · February 3, 2019 18:57 · Feb 3, 2019
diff --git a/README.md b/README.md
@@ -0,0 +1,39 @@
+# 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](https://leetcode.com/problems/subarray-sums-divisible-by-k/)
+[Solution Explained in Java](https://leetcode.com/problems/subarray-sums-divisible-by-k/discuss/217962/Java-Clean-O(n)-Number-Theory-%2B-Prefix-Sums)
diff --git a/solution.js b/solution.js
@@ -0,0 +1,37 @@
+/*
+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));