Check If Array Pairs Are Divisible by k

Check If Array Pairs Are Divisible by k

What is this problem about?

The "Check If Array Pairs Are Divisible by k interview question" asks you to determine if an array of integers can be partitioned into $n/2$ pairs such that the sum of each pair is divisible by a given integer k. For example, if k=10, a pair like (3, 7) or (13, 27) is valid because their sums (10 and 40) are multiples of 10.

Why is this asked in interviews?

Companies like Microsoft, Meta, and Google use the "Check If Array Pairs Are Divisible by k coding problem" to test a candidate's understanding of modular arithmetic and the "Hash Table interview pattern." It evaluates whether you can simplify a problem by focusing on the remainder of each number when divided by k, rather than the numbers themselves. It’s a core test of frequency counting logic.

Algorithmic pattern used

This problem follows the Frequency Counting with Modular Arithmetic pattern.

1. Calculate Remainder: For every number in the array, find its remainder when divided by k. Use the formula ((num % k) + k) % k to handle negative integers correctly.
2. Frequency Map: Store the count of each remainder in a hash map or an array of size k.
3. Pairing Logic:
   • Remainder 0: Numbers with remainder 0 can only pair with other numbers with remainder 0. The count of such numbers must be even.
   • Remainder i: A number with remainder i must pair with a number with remainder k - i. The counts of remainder i and remainder k - i must be identical.
   • Remainder k/2 (if $k$ is even): These must pair with each other, so their count must be even.

Example explanation

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

1. Remainder frequencies:
   • 0: {5, 10} -> Count 2 (Even, OK)
   • 1: {1, 6} -> Count 2
   • 2: {2, 7} -> Count 2
   • 3: {3, 8} -> Count 2
   • 4: {4, 9} -> Count 2
2. Match: Count(1) must equal Count(4). Both are 2. Count(2) must equal Count(3). Both are 2. Result: True.

Common mistakes candidates make

• Negative Remainder: Not handling negative numbers correctly (-1 % 5 is -1 in many languages, but should be treated as 4 for pairing).
• Even/Odd check for 0: Forgetting that remainder 0 elements can't pair with anything else but each other.
• Floating Point: Trying to use division instead of the modulo operator.

Interview preparation tip

Always normalize your data. In modular arithmetic problems, converting all inputs into their "remainder form" within the range [0, k-1] simplifies the logic immediately. This is a foundational "Math interview pattern."