Given an array of integersarr
of even lengthn
and an integerk
. We want to divide the array into exactlyn / 2
pairs such that the sum of each pair is divisible byk
. 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