Leetcode 1497 - Check If Array Pairs Are Divisible by k

Link to problem

Problem

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.

Approach

At first glance, I thought this is a bit similar to two sum, probably a bit more complex. Therefore, my first attempt was implementing the algorithm using hash map. As we know about the properties of remainder, if the sum two numbers are divisible by k, the sum of both number’s remainder divided by k will can be divided by k.

Solution

1. Form a hash map remainderCount, which stores the number of different remainders using arr. But keep in mind that there are negative numbers in the test cases. However, we could solve this problem by shifting the input numbers by adding k after doing mod k. By doing so we are sure that all the numbers will be positive integers. But now the numbers are not the remainder of k, so do another mod k to it.

2. Now having the hash map ready, we could now determine the result using the following conditions when iterating through the hashmap:

   A. Remainder equals to 0. This in this case we need to check if the number that has remainder of 0 is even or not. If it is odd, then we could not pair it and should return false.

   B. We could not found number with remainder equals to k - iterated remainder , which means we could not find a number that combined with the iterated number that could be divisible by k.

   C. There exist k - iterated number and in order to pair those number, the count of the iterated number must equal to the count of k - iterated number. If they are not equal, we could not pair it, return false.

3. If every number passes the condition mentioned above, that means we could pair every number in the input array to be divisible by k. Return true.

Implementation

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        unordered_map<int, int> remainderCount;

        for (int i = 0; i < arr.size(); i++) {
            arr[i] = (arr[i] % k) + k;
            remainderCount[arr[i] % k]++;
        }      

        for (auto p: remainderCount) {
            if (p.first == 0) {
                if (p.second % 2 != 0) return false;
            }
            else if (remainderCount.find(k - p.first) == remainderCount.end()) {
                return false;
            }
            else if (remainderCount[k - p.first] != p.second) {
                return false;
            }
        }

        return true;
    }
};