Your random JavaScript coding question of the day — Day 1
As software engineers, we are so busy working on our jobs that sometimes we forget the basics and where we all began. After working for over 8 years as a software engineer, I recently took a much-needed break to take care of some personal goals. But that itch for coding keeps coming back so I decided to solve random coding questions daily to keep myself sharp. Some days I will solve hard problems but today let's start with an easy one!
Problem
Given an array of integers and a positive integer k
, determine the number of (i, j)
pairs where i < j
and arr[i] + arr[j]
is divisible by k
.
Example:
arr = [1, 2, 3, 4, 5, 6]
k = 5
Three pairs meet the criteria: [1, 4]
, [2, 3]
, and [4, 6]
.
Solution
Let’s dive into the solution and its analysis.
Naive Solution
This is a simple solution that first comes to mind when we look at this problem.
- Start by iterating through each element in the array.
- For each number, iterate through the array again starting from the next element.
- In the nested iteration, check if the sum of the two numbers we are looking at is divisible by
k
. - If the sum is divisible by
k
, increment the count of valid pairs.
Here’s the JS implementation of the naive approach.
function divisibleSumPairs(arr, k) {
let count = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if ((arr[i] + arr[j]) % k === 0) {
count++;
}
}
}
return count;
}
// Example usage
const arr = [1, 2, 3, 4, 5, 6];
const k = 5;
console.log(divisibleSumPairs(arr, k)); // Output: 3
Problem With The Naive Approach
This solution works well in many real-world scenarios but since it iterates through every possible pair in the array, checking if their sum is divisible by k
, it has a major drawback: the time complexity is O(n²)
. For large arrays, this quickly becomes inefficient. For an array of length n
, the number of iterations required is n(n-1)/2
, which is prohibitively expensive for large n
.
Optimal Solution
The key concept we will use for the optimal solution is — When you divide a number by k
, the remainder (let’s call it currentRemainder
) is a value between 0 and k-1
. For two numbers to sum up to a multiple of k
, the sum of their remainders must be k
or 0 (since k % k = 0
).
By using this modular arithmetic and a hash map (or object in JavaScript), we can achieve an O(n)
solution. The idea is to use a hash map to keep track of remainders when elements are divided by k
.
Steps for the Optimal Solution
- Initialize a hash map to store the count of remainders.
- Iterate through the array and for each element:
- Calculate its remainder when divided by
k
. - Determine the complement remainder needed to form a sum divisible by
k
. - Check the hash map for the complement remainder and update the count of valid pairs.
- Update the hash map with the current element’s remainder.
Code for the Optimal Solution
Here’s the implementation in JavaScript:
function divisibleSumPairs(arr, k) {
let count = 0;
let remainderCounts = {};
for (const num of arr) {
const currentRemainder = num % k;
const complementRemainder = (k - currentRemainder) % k;
// Check if the complement remainder exists in the hash map
if (complementRemainder in remainderCounts) {
count += remainderCounts[complementRemainder];
}
// Update the hash map with the current remainder
if (!(currentRemainder in remainderCounts)) {
remainderCounts[currentRemainder] = 0;
}
remainderCounts[currentRemainder]++;
}
return count;
}
// Example usage
const arr = [1, 2, 3, 4, 5, 6];
const k = 5;
console.log(divisibleSumPairs(arr, k)); // Output: 3
Breaking Down the Optimal Solution
1. Initialization
count
is initialized to 0 to store the number of valid pairs.remainderCounts
is an object (hash map) to keep track of the counts of each remainder.
2. Traversal and Counting
For each element in the array:
- Calculate the
currentRemainder
when divided byk
. - Calculate the
complementRemainder
that would make the sum divisible byk
. - If the
complementRemainder
is present in the hash map, add its count tocount
. - Update the hash map with the current element’s remainder.
Conclusion
By switching from a naive nested loop approach to a more efficient hash map-based solution, we dramatically improve the performance of our algorithm. This demonstrates the power of optimizing algorithms using clever data structures and mathematical insights.
The next time you encounter a similar problem, remember that sometimes a small change in approach can lead to significant improvements in efficiency. Happy coding!