Your random JavaScript coding question of the day — Day 1

Photo by Oskar Yildiz on Unsplash

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 < jand 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.

1. Start by iterating through each element in the array.
2. For each number, iterate through the array again starting from the next element.
3. In the nested iteration, check if the sum of the two numbers we are looking at is divisible by k.
4. 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 kor 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

1. Initialize a hash map to store the count of remainders.
2. 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 by k.
• Calculate the complementRemainder that would make the sum divisible by k.
• If the complementRemainder is present in the hash map, add its count to count.
• 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!