1497. Check If Array Pairs Are Divisible by k

Description

The problem is to check if an array of integers can be rearranged into pairs such that the sum of each pair is divisible by a given integer k. Given an array arr and an integer k, we need to determine if it's possible to arrange the array into pairs where the sum of the two integers in each pair is divisible by k.

Intuition

The main observation is that for two numbers to form a valid pair, their remainders when divided by k must complement each other to sum to k. For example, if one number has a remainder of r, the other must have a remainder of k - r for their sum to be divisible by k. Special cases arise when the remainder is 0 (i.e., the number is divisible by k), in which case the number must pair with another number that is also divisible by k.

Approach

1. Create a frequency array to count how many numbers give each remainder when divided by k.
2. Traverse through the array and update the remainder counts.
3. First, check if the number of elements with a remainder of 0 is even because they must pair with each other.
4. For all other remainders, ensure that the count of numbers with a remainder of i matches the count of numbers with a remainder of k - i.
5. If any condition fails, return false. Otherwise, return true.

Complexity

• Time Complexity: O(n), where n is the size of the array. We iterate through the array once to calculate the remainders and verify the conditions.
• Space Complexity: O(k), where k is the divisor. We store frequency counts for each possible remainder.

Code

C++

class Solution {
public:
    bool canArrange(std::vector& arr, int k) {
        std::vector freq(k, 0);

        for (int num : arr) {
            int rem = num % k;
            if (rem < 0) {
                rem += k;
            }
            freq[rem]++;
        }

        if (freq[0] % 2 != 0) {
            return false;
        }

        for (int i = 1; i <= k / 2; i++) {
            if (freq[i] != freq[k - i]) {
                return false;
            }
        }

        return true;
    }
};

Python

class Solution:
    def canArrange(self, arr, k):
        freq = [0] * k

        for num in arr:
            rem = num % k
            if rem < 0:
                rem += k
            freq[rem] += 1

        if freq[0] % 2 != 0:
            return False

        for i in range(1, k // 2 + 1):
            if freq[i] != freq[k - i]:
                return False

        return True

Java

public class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] freq = new int[k];

        for (int num : arr) {
            int rem = num % k;
            if (rem < 0) {
                rem += k;
            }
            freq[rem]++;
        }

        if (freq[0] % 2 != 0) {
            return false;
        }

        for (int i = 1; i <= k / 2; i++) {
            if (freq[i] != freq[k - i]) {
                return false;
            }
        }

        return true;
    }
}

JavaScript

var canArrange = function (arr, k) {
    const freq = new Array(k).fill(0);

    for (const num of arr) {
        let rem = num % k;
        if (rem < 0) {
            rem += k;
        }
        freq[rem]++;
    }

    if (freq[0] % 2 !== 0) {
        return false;
    }

    for (let i = 1; i <= Math.floor(k / 2); i++) {
        if (freq[i] !== freq[k - i]) {
            return false;
        }
    }

    return true;
};