Teaching Kids Programming – Partition List to Pairs that Are Divisible by K (Hash Map)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums and an integer k, return whether the list can be partitioned into pairs such that each pair’s sum is divisible by k.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [4, 8, 2, 1]
k = 3
Output
True
Explanation
We can partition the list into pairs (4, 2) and (8, 1) and their sums are divisible by 3.

Observations:
If list length is odd or list sum is not divisible by k then answer is false.
Now think how elements % k will help ?

Partition List to Pairs that Are Divisible by K (Hash Map)

We can use a dictionary aka hash map to store the frequencies for the remainder by K. Thus, we can pair numbers by remainder, e.g. remainder i should be paired with remainder k-i. Special case is when remainder is zero (divisble by k), the numbers should be paired also with those are multiples of K.

Assume a pair is (a, b), we have:

Given:
Thus:
So:

Given we have counted the frqeuencies of the remainder, we have to check if the corresponding group having the same quantity so that we can pair them. Otherwise we can’t pair all numbers to be divisible by K.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def solve(self, nums, k):
        if len(nums) & 1:
            return False
 
        s = defaultdict(int)
        for x in nums:
            s[x % k] += 1
 
        if s[0] & 1:
            return False
 
        return all(s[i] == s[k - i] for i in range(1, k))

class Solution:
    def solve(self, nums, k):
        if len(nums) & 1:
            return False

        s = defaultdict(int)
        for x in nums:
            s[x % k] += 1

        if s[0] & 1:
            return False

        return all(s[i] == s[k - i] for i in range(1, k))

The time complexity is O(N) and the space complexity is O(N) as we need a dictionary to store the frequencies of remainder. Another approach slightly different:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def solve(self, nums, k):
        f = defaultdict(int)
        c = 0
        for i in nums:
            a = i % k
            b = (k - a) % k
            if f[a] > 0:
                f[a] -= 1
                c -= 1
            else:
                f[b] += 1
                c += 1
        return c == 0

class Solution:
    def solve(self, nums, k):
        f = defaultdict(int)
        c = 0
        for i in nums:
            a = i % k
            b = (k - a) % k
            if f[a] > 0:
                f[a] -= 1
                c -= 1
            else:
                f[b] += 1
                c += 1
        return c == 0

Basically, we iterate over the numbers, and for each number, we know the pair, so we check their appearance, and adjust the counter accordingly. If we can form pairs, the counter will be finally zero. O(N) time/space complexity.

–EOF (The Ultimate Computing & Technology Blog) —