Check If Array Pairs Are Divisible by k

The problem requires us to find if we can divide the array into exactly ( n / 2 ) pairs such that the sum of each pair is divisible by ( k ).

Here’s a way to approach the problem, starting simple and then going into more details:

Key Insight

The remainder when dividing a number by ( k ) will determine its compatibility with other numbers. We’ll have to match numbers with complementary remainders so that their sum is divisible by ( k ).

Algorithm

1. Calculate Remainders: For each element in the array, calculate the remainder when dividing by ( k ), and keep track of the frequency of each remainder.
2. Match Complementary Remainders: For each unique remainder ( r ), check if there are an equal number of elements that have a remainder of ( (k - r) ) or ( r ). These are complementary remainders.
3. Special Case for Remainder 0: If there are numbers that are exactly divisible by ( k ) (remainder 0), then there should be an even number of them to form pairs.

Implementation

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        remainder_count = [0] * k

        # Step 1: Calculate the remainders and their counts
        for num in arr:
            remainder_count[num % k] += 1

        # Step 2: Check for complementary remainders
        for i in range(1, (k + 1) // 2):
            if remainder_count[i] != remainder_count[k - i]:
                return False

        # Step 3: Check for remainder 0
        if remainder_count[0] % 2 != 0:
            return False

        return True

Example

For the input ( arr = [1,2,3,4,5,10,6,7,8,9], k = 5 ), the remainders are [0, 1, 1, 2, 2, 0, 1, 2, 3, 4]. By using the above method, we can find the pairs as described and return true.

Time Complexity

The time complexity of this solution is ( O(n + k) ), where ( n ) is the length of the array, and ( k ) is the given integer.

Summary

• Calculate the remainder of each number with ( k ) and count the occurrences.
• Match the complementary remainders.
• Special handling for remainder 0.
• Check if the solution works for each given example to validate the approach.