Skip to content

Instantly share code, notes, and snippets.

@josgraha

josgraha/README.md

Created February 3, 2019 18:57
Show Gist options
  • Save josgraha/2e6fb38c0e466273db4c624b7f6eba72 to your computer and use it in GitHub Desktop.
Save josgraha/2e6fb38c0e466273db4c624b7f6eba72 to your computer and use it in GitHub Desktop.
Download ZIP
Find max subarray divisible by K
Raw
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

Raw
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));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment