Sep 10, 2016

This past week at Viking Code School we were introduced to Javascript. It’s been an interesting transition from the friendly, English-like syntax of Ruby to the harsh, low-level feel of Javascript. It certainly doesn’t hold your hand, that’s for certain. On the bright side Javascript makes good use of first-class functions and callbacks, which certainly lends it a sense of flexibility if not neatness. That said, this week I will be covering an algorithm in Javascript rather than the usual Ruby, so let’s get cracking!

Suppose that you are given an array A of n integers. You are also given a positive integer k. Your task is to find and print the total number of (i, j) such that i < j and A[i] + A[j] is evenly divisible by k. Think you could do it? Let’s take a look at a potential naive approach.

```
var pairs = function(n, k, arr) {
count = 0;
for (var i = 0; i < n; i++){
for (var j =0; j < n; j++) {
if (i < j && (arr[i] + arr[j]) % k === 0) {
count++;
}
}
}
return count;
};
```

This is fairly straightforward, we just create a nested loop structure so that we are iterating through every possible pair of numbers in our array, A. Unfortunately, this means that we are exploring quite a few dead ends since our problem statement excluded all pairs such that i >= j. In fact, this solution comes in at a leisurely O(n²) in terms of Big-Oh notation with respect to time. We can do better.

Wouldn’t it be nice if we only had to iterate through the list once? Let’s see if we can. Here’s just such a solution:

```
var pairs = function(n, k, arr) {
var count = 0;
var counts = {};
for(var i = 0; i < n; i++) {
var bucket = arr[i] % k;
// add all of the complementary buckets to the count
if (counts[(k - bucket) % k]) { count += counts[(k - bucket) % k]; }
// increment this bucket's count
if (counts[bucket]) { counts[bucket] += 1; } else { counts[bucket] = 1; }
}
return count; // return all of the found matches
};
```

This solution exploits a quirk of Modular Arithmetic, specifically the statement that:

```
(A+B) mod C = ((A mod C) + (B mod C)) mod C
```

This means that we can decouple the observation that A[i] + A[j] ought to be divisible by k into two separate observations, namely that A[i] % k + A[j] % k ought to be divisible by k.

So we iterate through A and for each element, we determine which “bucket” it falls into, e.g. 5 % (k=3) == 2, so we would increment the “2” bucket. Simultaneously we increment each time we find an element that can be considered complementary with any terms we’ve categorized before. If we’ve already incremented our “2” bucket and we come across a term that falls under the “1” bucket, we can increment our total count of pairs that satisfy the problem statement since (2 + 1) % 3 == 0.

This one can be a little tough to wrap your head around, but is quite satisfying once you get it. I hope you’ve enjoyed this week’s algorithm, and I look forward to bringing you more mathematical goodness next week!