# Solving Leetcode Interviews in Seconds with AI: Check If Array Pairs Are Divisible by k


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1497" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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.   Example 1:  Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5 Output: true Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).  Example 2:  Input: arr = [1,2,3,4,5,6], k = 7 Output: true Explanation: Pairs are (1,6),(2,5) and(3,4).  Example 3:  Input: arr = [1,2,3,4,5,6], k = 10 Output: false Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.    Constraints:  arr.length == n 1 <= n <= 105 n is even. -109 <= arr[i] <= 109 1 <= k <= 105  

	# Explanation
	Here's the breakdown of the solution:

*   **Residue Counting:** The core idea is to count the frequency of each residue (remainder) when the numbers in the array are divided by `k`.
*   **Pair Matching:** For each residue `r`, we need to find a corresponding residue `k - r` such that their counts match.  If the count of `r` does not equal the count of `k-r`, it's impossible to form the required pairs. Special handling is needed for the residue `0` and `k/2` if k is even because their complement is themselves.
*   **Early Exit:** If, at any point, we find a mismatch in the counts, we can immediately return `False`.

*   **Runtime Complexity: O(n), Storage Complexity: O(k)**

	
	# Code
	```python
	def can_arrange(arr: list[int], k: int) -> bool:
    """
    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.

    Example 1:
    Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
    Output: true
    Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

    Example 2:
    Input: arr = [1,2,3,4,5,6], k = 7
    Output: true
    Explanation: Pairs are (1,6),(2,5) and(3,4).

    Example 3:
    Input: arr = [1,2,3,4,5,6], k = 10
    Output: false
    Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.

    Constraints:
    arr.length == n
    1 <= n <= 105
    n is even.
    -109 <= arr[i] <= 109
    1 <= k <= 105
    """
    remainders = {}
    for num in arr:
        remainder = num % k
        remainders[remainder] = remainders.get(remainder, 0) + 1

    for remainder in remainders:
        if remainder == 0:
            if remainders[remainder] % 2 != 0:
                return False
        elif 2 * remainder == k:
            if remainders[remainder] % 2 != 0:
                return False
        elif remainder not in remainders or (k - remainder) not in remainders or remainders[remainder] != remainders[k - remainder]:
            return False
    return True
	```