[Leetcode]1497. Check If Array Pairs Are Divisible by k

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.
 
Example 1:
Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5 Output: true 
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

This question first appeared in the Leetcode weekly contest 195. It borrows the idea from Two Sum that, for each number, we would try to find its complementary number by storing its remainder in a hashmap. The following two approaches are from @rajmc and @101leetcode.

Logic

The core idea is that, if a \% k=i (i \neq 0) and b \% k=k-i, then (a+b) \% k =0. With this being said, we could simply store the remainders and check whether we could pair the remainders i with their partners k-i. Notably, when i=0, its partner should also have the remainder of 0.

Moreover, different programming languages deal with divisions on negatives in different ways. This post tells more about it: Why Python’s Integer Division Floors.

Simply speaking, with the equation a/b=q with the remainder r, when a is negative and b is positive, Java and C++ would ceil(q) so that r becomes negative while Python would floor(q) so that r is positive. Both of them preserve the relation that b*q+r=a.

Therefore, in Python, the remainder always has the same sign as the denominator, while in Java and C++ that’s not the case. Thus, if you use Java and C++, when the reminder i<0, you need one more step as i+=k. That’s because -2%5 is the same as (-2+5)%5 – they both need 2%5.

Code

The first way of programming is to implement exactly what the logic instructs. Note that for those numbers divisible by k, their partner should also have 0 as the remainders, and the numbers of elements divisible by k should be even.

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        dic = collections.defaultdict(int)
        # store the remainders
        for num in arr:
            reminder = num % k
            if reminder < 0:
                reminder += k
            dic[reminder] += 1
        # check divisibles
        if dic[0] % 2 != 0:
            return False
        # check dic[i] == dic[k-i]:
        for i in range(1,k//2+1):
            if dic[i] != dic[k-i]:
                return False
        return True

Another way of implementation is that we can greedily find the partner for each number, if we can’t find it, then we need to store the number in the hashmap for further pairing. Finally if there are keys left in the hashmap, return False.

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        dic = collections.defaultdict(int)
        for num in arr:
            key = k - num % k
            # find its partner
            if dic.get(key):
                dic[key] -= 1
                if dic[key] == 0:
                    dic.pop(key)
            else: # if no partner found, add it to the hashmap
                dic[num % k or k] += 1
        return not dic