Leetcode Daily Question 01/10/2024 - 1497. Check If Array Pairs Are Divisible by k

Problem Description:

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.

from typing import List
from collections import Counter
class Solution
  def canArrange(self, arr: List[int], k: int) -> bool:
    arr = [num % k for num in arr]
    freq_counter = Counter(arr)
    
    for i in range(1, k // 2 + 1):
      if freq_counter[i] != freq_counter[k - i]:
        return False
    
    return k % 2 == 1 or freq_counter[k // 2] % 2 == 0

Explanation:

We use modular arithmetic to count pairs achieved.

To form valid pairs, the sum of the remainders of two elements must be divisible by k. This means for each remainder i, we need another remainder k - i to form a valid pair.

We call such a pair a "modded complement pair".

We need every the frequency of modded complement pair in [1, k//2] to match to potentially produce enough pairs.

If k is odd, then we already have enough pairs as i != k - i for any i.

If k is even, then we have i == k - i when i == k // 2. This means the modded complement pair is itself added together. Meaning, we need to know if this count is even to form the last pair needed.

def canArrange(arr, k):
  arr = [num % k for num in arr] # mod all elements to help find the modded complement pairs.
  freq_counter = Counter(arr) # Counter() method from collections counts frequency of elements
  
  for i in range(1, k // 2 + 1):
    if freq_counter[i] != freq_counter[k-i]:
      return False
    
  return k % 2 == 1 or freq_counter[k // 2] % 2 == 0

The time complexity is O(n) as we need to iterate through arr to mod every element.

The space complexity is O(n) as we need to store this new modded version of arr, as well as a Counter object to counter frequencies O(k) < O(n).

The full solution can be found near the top of the page.