Code Implementation

from collections import Counter

class Solution:
    def canArrange(self, arr, k):
        count = Counter()
        for num in arr:
            remainder = num % k
            count[remainder] += 1

        for rem in count:
            if rem == 0:
                if count[rem] % 2 != 0:
                    return False
            elif 2 * rem == k:
                if count[rem] % 2 != 0:
                    return False
            else:
                if count[rem] != count[k - rem]:
                    return False
        return True
      

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        unordered_map<int, int> count;
        for (int num : arr) {
            int rem = ((num % k) + k) % k;
            count[rem]++;
        }
        for (auto it : count) {
            int rem = it.first;
            if (rem == 0) {
                if (count[rem] % 2 != 0) return false;
            } else if (2 * rem == k) {
                if (count[rem] % 2 != 0) return false;
            } else {
                if (count[rem] != count[k - rem]) return false;
            }
        }
        return true;
    }
};
      

import java.util.*;

class Solution {
    public boolean canArrange(int[] arr, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : arr) {
            int rem = ((num % k) + k) % k;
            count.put(rem, count.getOrDefault(rem, 0) + 1);
        }
        for (int rem : count.keySet()) {
            if (rem == 0) {
                if (count.get(rem) % 2 != 0) return false;
            } else if (2 * rem == k) {
                if (count.get(rem) % 2 != 0) return false;
            } else {
                if (!count.get(rem).equals(count.getOrDefault(k - rem, 0))) return false;
            }
        }
        return true;
    }
}
      

var canArrange = function(arr, k) {
    let count = new Map();
    for (let num of arr) {
        let rem = ((num % k) + k) % k;
        count.set(rem, (count.get(rem) || 0) + 1);
    }
    for (let [rem, val] of count.entries()) {
        if (rem === 0) {
            if (val % 2 !== 0) return false;
        } else if (2 * rem === k) {
            if (val % 2 !== 0) return false;
        } else {
            if (val !== (count.get(k - rem) || 0)) return false;
        }
    }
    return true;
};
      

Problem Description

Given an array of integers arr and an integer k, determine if it is possible to rearrange the elements of arr into pairs such that the sum of each pair is divisible by k. Each element in arr must be used exactly once, and each pair must consist of two distinct (not necessarily different) elements from the array.

• Each element must be used in exactly one pair (no element reuse).
• Pairs can be in any order.
• The sum of each pair must be divisible by k.
• If such a rearrangement is possible, return true; otherwise, return false.

Thought Process

At first glance, it may seem that we need to try all possible pairings, checking if each pair sums to a multiple of k. However, this brute-force approach is inefficient and impractical for large arrays.

To optimize, we should focus on the remainders of the numbers when divided by k. If two numbers have remainders r1 and r2, their sum is divisible by k if and only if (r1 + r2) % k == 0. This means r2 = k - r1 (or both are zero).

So, instead of checking all pairs, we can count how many numbers have each possible remainder, and then check if the counts can be paired up appropriately.

Solution Approach

• Step 1: Compute the remainder of each element in arr when divided by k. For negative numbers, adjust the remainder to be in the range 0 to k-1.
• Step 2: Count how many elements have each remainder using a hash map or array.
• Step 3: For each possible remainder rem:
  • If rem == 0: There must be an even number of such elements, since they must pair with each other.
  • If 2 * rem == k (when k is even): These remainders must also be paired among themselves, so their count must be even.
  • Otherwise: The count of elements with remainder rem must equal the count with remainder k - rem, because each such pair together sums to a multiple of k.
• Step 4: If all these conditions are met, return true. Otherwise, return false.

We use a hash map for efficient counting and lookups, ensuring the algorithm runs in linear time.

Example Walkthrough

Example: arr = [1,2,3,4,5,10,6,7,8,9], k = 5

1. Compute remainders:
   • 1 % 5 = 1
   • 2 % 5 = 2
   • 3 % 5 = 3
   • 4 % 5 = 4
   • 5 % 5 = 0
   • 10 % 5 = 0
   • 6 % 5 = 1
   • 7 % 5 = 2
   • 8 % 5 = 3
   • 9 % 5 = 4
2. Count of remainders:
   • 0: 2
   • 1: 2
   • 2: 2
   • 3: 2
   • 4: 2
3. Check pairing conditions:
   • Remainder 0: count is 2 (even) - OK
   • Remainder 1 and 4: counts are both 2 - OK
   • Remainder 2 and 3: counts are both 2 - OK
4. All conditions are satisfied, so the answer is true.

The array can be paired as (1,4), (2,3), (5,10), (6,9), (7,8) where each pair sums to a multiple of 5.

Time and Space Complexity

• Brute-force approach: Trying all pairings would be O(n!), which is infeasible for large arrays.
• Optimized approach:
  • Time Complexity: O(n), where n is the length of arr. We scan the array once to compute remainders and once to check the pairing conditions.
  • Space Complexity: O(k), for storing counts of each possible remainder.

The optimized approach is efficient and suitable for large inputs.

Summary

By focusing on the remainders of each element modulo k and counting their frequencies, we reduce the problem of pairwise matching to a simple counting problem. The key insight is that for each remainder, there must be a matching count of its complement to form valid pairs. This leads to a clean and efficient solution that avoids brute-force enumeration, making the algorithm both elegant and performant.