Hacker Rank problems can be fun, and I often find myself learning something interesting. I recently undertook the Divisible Sum Pairs problem.
In short, given an array of integers ar, and an integer k, find how many pairs of integers add up to a multiple of k.
The trivial solution is just a double for-loop that has an O(n^2) run-time.
I often find that by the time I’m done reading through the Hacker Rank problems and go start working through the actual code to solve the problem, that I’ve let a key detail slip. Such was the case this time, and my original solution found the total of the pairs of integers that added up to k rather than a multiple of k.
Because of that, my initial implementation used a hash table, and I decided to try and expand out my initial hash table solution to deal with multiples. Here is my solution:
function divisibleSumPairs(n, k, ar) {
let myMap = new Map();
let pairs = 0;
let biggestValue = ar[0];
for(let i=0;i<ar.length;i++) {
let maxLookingFor = ar[i] + biggestValue;
let iterations = Math.ceil(maxLookingFor/k);
for(let j=1; j<=iterations;j++) {
let lookingFor = k*j-ar[i];
const mapValue = myMap.get(lookingFor)
if(mapValue) {
pairs += mapValue;
}
}
if(ar[i] > biggestValue) {
biggestValue = ar[i];
}
const mapValue = myMap.get(ar[i]);
if(mapValue) {
myMap.set(ar[i], mapValue + 1);
} else {
myMap.set(ar[i], 1);
}
}
return pairs;
}
Here is the least efficient:
function divisibleSumPairs(n, k, ar) {
let pairs = 0;
for(let i=0;i<ar.length;i++) {
for(let j=i+1;j<ar.length;j++) {
let sum = ar[i] + ar[j];
if(!(sum%k)) { //!sum%k does !sum then %k's the !sum
pairs++;
}
}
}
return pairs;
}
Here’s the most efficient solution:
function divisibleSumPairs(n, k, ar) {
let numbers = [];
for(let i=0;i<k;i++) { numbers.push([]); }
for(let i=0;i<ar.length;i++) { let remainder = ar[i]%k; numbers[remainder].push(ar[i]); }
let count;
//populate the zero row let zeroQuantity = numbers[0].length;
count = (zeroQuantity * (zeroQuantity -1)) / 2;
let j = k -1;
//populate the remaining rows
for(let i=1; i<=j;i++) {
if(i == j) {
//remainders add to k
let middleRowQuantity = numbers[i].length;
count += (middleRowQuantity * (middleRowQuantity - 1)) / 2;
} else {
//remainder is exactly half k
count += numbers[i].length * numbers[j].length;
}
j--;
}
return count;
}
As k gets smaller, the range of numbers gets bigger, and the length of the array ar gets smaller, the ‘worst’ alogorithm will tend to do better compared to my solution. As k gets larger, the range of numbers gets smaller, and the size of the array gets larger, then my solution will tend to perform better.
The most efficient solution is obviously better than either of the other two. If we were talking a problem where the range of numbers in the array was very small, or the range was very small until the last step, k was very large, and we needed the pairs returned, then it’s possible that the generation of the pairs at the end of the efficient solution could take longer than my solution, but that’s a pretty extreme, narrow kind of edge case.
If I ever run into a similar problem in the wild, I’ll now know how to approach it thanks to the commenters in the discussion section on Hacker Rank.
