calculate the number of ways to pick two different indices

Question

I'm working on a codesignal practice problem

You are given an array of integers a and an integer k. Your task is to calculate the number of ways to pick two different indices i < j, such that a[i] + a[j] is divisible by k.

Guaranteed constraints:

• 1 ≤ a.length ≤ 10^5,
  

• 1 ≤ a[i] ≤ 10^9.
  

Now, the problem is super easy to brute force, but I'm hitting the 4s execution time limit on the later test cases. How can I optimize my solution so I can pass the later test cases?

function solution(a, k) {
    let count = 0
    
    for (let i = 0; i < a.length - 1; i++) {
        for (let e = i + 1; e < a.length; e++) {
            if ((a[i] + a[e]) % k === 0) count = count + 1
        }
    }

    return count
}

I've gotten a tip to convert the array to an array of moduluses and then use that ( and seen a couple solutions that also do that), but I don't see what I can do with that besides just loop over that new array the same way.

Answer 1

use boring business vocabulary

Your task ... two different indices i < j, such that a[i] + a[j] ...

        for (let e = ...
            if ((a[i] + a[e]) ...

What happened here?

If the language of the business requirements uses Widgets or Yoyodynes, then incorporate those terms into your identifiers.

It's unclear why you arbitrarily went from j to e. It could have been clear, if you made a decision and then documented that decision in a // comment. As written, it's just a needless cognitive speed bump.

---

simplify

a tip ... don't see what I can do with that

The original problem is too hard. That's fine. Many problems are too hard. After some study, they become easier.

So let's ignore the original requirements, let's pretend that K is always 2, and ask whether that is a solvable problem, an easy problem. K = 2 implies that we only care about whether a number is odd vs even. a[i] will be one of those numbers, as will a[j], and also the sum. We only increment upon finding an even sum.

So let's take a step back. How shall we arrive at an even sum? Let's see, even + even, also odd + odd, those look good. But even + odd, or odd + even? No. So create a list of indexes i where a[i] is even, and another for the odd case.

Now iterate through the evens, with nested iteration through the evens, and output those winning sums. Oh, wait! "Output" is just a matter of incrementing count. And we don't even need to do O(N²) iterations across upper triangle of N evens, since there's an analytic formula: count += N * (N-1) / 2.

Good, now let's pick up the odds. Oh, wait, it's essentially the same situation. So again, revising it to N odd entries this time, a formula lets us add to count.

generalize

That was fun. Now we have confidence that There Must Be A Better Way. But what if K is sometimes bigger than two? We need to generalize.

We were examining even sums, that is, sum == 0 % 2. We had one term for evens (0 mod 2), and another term for odds (1 % 2). For this bigger problem we will need K terms.

Here's the good news. Do we need to allocate storage for all the evens, or all the "equal to zero mod K" numbers? No. Merely knowing how many we have suffices, that's what the simplified problem setup taught us.

All right. Allocate an array c of K entries. Rip through the various a numbers, and for each one increment c[a[i] % K]. If K is two we've now counted the evens and odds. And in the more general case we have a bunch of useful counts, more than two of them.

Now consider all the ways we can drive that sum to zero mod K. That's right, there's only K such ways. Tell me what we started with, and I will tell you the single possible way that the sum works out to zero. It's simple, for an integer i we're going to need to add K - i. We saw it work out in the odd/even setting, and it works in this setting as well.

Time for an action plan.

---

• Init count = 0.
• Allocate an array c of K entries.
• Fill in each c[i] entry with the number of a entries equal to i mod K.
• Loop over all i less than K:
• • Increment count by c[i] * c[K - i] / 2
• Return count.