Check If Array Pairs Are Divisible by k (LeetCode 1497)

Below is the problem statement for LeetCode 1497:

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return True If you can find a way to do that or False otherwise.

This problem caused a little bit of a controversy on LeetCode.

A Simple and Incorrect Solution

The reason behind the controversy was the following solution:

Sum up the elements in arr
Return true if sum % k == 0, else return false

That’s it! I first saw this solution after implementing my own solution. I felt a little silly having written something more complicated. But this solution is incorrect.

Consider the following input:

arr = [1, 1, 1, 1, 1], k = 5

The above algorithm will return true for this input when it should be false. No pair in the array is divisible by 5 but if you add them all up you get a sum divisible by 5. This is because the condition of sum % k == 0 is a necessary condition but not a sufficient condition. The condition will hold in every case that there is a solution. But not every case where the condition is true has a solution.

The Real Solution

Now let’s figure out the real solution.

What does it mean for a number to be divisible by k? We can describe this with the modulo operator %:

A number n is divisible by k if n % k == 0.

So if we have two elements x_i and x_j in our array, we know that their sum is divisible by k if:

(x_i + x_j) % k == 0

We can rewrite this as:

(a_ik + r_i + a_jk + r_j) % k == 0

In the above expression a_i = x_i/k and a_j = s_j/k in terms of integer division (e.g. 1/2 == 0) and r_i and r_j are the remainders modulo k. We can simplify the above expression by removing the terms a_ik and a_jk since they are 0 modulo k. This gives us:

(r_i + r_j) % k == 0

This means that what we’re looking for is pairs where the sum of their remainders is 0 modulo k. Because the remainders are less than k, there are only two cases where the sum of their remainders are 0 modulo k:

Both r_i and r_j are 0
r_i == k - r_j

We can actually combine these into one condition:

r_i == (k - r_j) % k

We now have everything in place to develop the algorithm.

We can create an array of size k, where the value at index i represents how many numbers n in the input array satisfy n % k == i. First we iterate over the input array and fill out are array of remainder counts. Then we loop over the remainder count array. We compare the value at index i to the value at index (k - i) % k. There’s two different cases to consider:

i != (k - i) % k
i == (k - i) % k

If i != (k - i) % k, all we need to do is compare the counts. If the counts are different we return false because this means there exist numbers that can’t be paired.

If i == (k - i) % k then what we need to check is that the value at i is even. This is because we’re pairing off numbers with the same remainder. Hence the number of elements with that remainder has to be divisible into pairs i.e. even.

Below is Ruby code implementing this algorithm. Annotated with comments at the top, no comment code further below:

def can_arrange(arr, k)
  # Initialize an array of remainder counts
  # Index 0 corresponds to remainder 0, index 1 remainder 1, etc.
  remainders = [0] * k
  # Calculate remainder modulo k and increment the count for that remainder
  arr.each { |n| remainders[n % k] += 1 }
  # loop over all possible remainders and ensure pairs are possible
  (0..k-1).all? do |remainder|
    # "complementary remainder" i.e. (remainder + complement) % k == 0
    complement = (k - remainder) % k
    # if the remainder and the complement are equal, the number of elements
    # with that remainder must be even. That way they can all be paired off
    # with another element of the same remainder.
    if remainder == complement
      remainders[remainder] % 2 == 0
    # if the remainder does not equal the complement, we have to ensure their
    # counts are the same so that they can be paired off
    else
      remainders[remainder] == remainders[complement]
    end
  end
end

And without the comments below:

def can_arrange(arr, k)
  remainders = [0] * k
  arr.each { |n| remainders[n % k] += 1 }
  (0..k-1).all? do |remainder|
    complement = (k - remainder) % k
    if remainder == complement
      remainders[remainder] % 2 == 0
    else
      remainders[remainder] == remainders[complement]
    end
  end
end