Check if array pairs are divisible by k

XXX. Check if Array Pairs Are Divisible by k

Hash Map

Mathematics

Problem Statement:

Given an integer array arr and an integer k, determine if it is possible to rearrange the array such that the sum of every pair of elements is divisible by k.

Algorithm:

The solution uses a hash map to store the frequency of remainders when elements are divided by k. The key observations are:

1. For each number i in the array, calculate its remainder when divided by k. Adjust the remainder to always be non-negative.
2. Count the frequency of each remainder using a hash map.
3. Check the following conditions:
   • For elements with a remainder of 0, their count must be even since they can only pair with each other.
   • For elements with remainder r, their count must equal the count of elements with remainder k - r.

Complexity:

Time Complexity: O(n), where n is the size of the array. Each element is processed once.
Space Complexity: O(k), as the hash map stores remainders from 0 to k-1.

Java Implementation:

public class Solution {
    public boolean canArrange(int[] arr, int k) {
        Map remainderCount = new HashMap<>();

        // Store the count of remainders in a map.
        for (int i : arr) {
            int rem = ((i % k) + k) % k; // Ensure non-negative remainder
            remainderCount.put(rem, remainderCount.getOrDefault(rem, 0) + 1);
        }

        for (int i : arr) {
            int rem = ((i % k) + k) % k;

            // If the remainder is 0, its count must be even
            if (rem == 0) {
                if (remainderCount.get(rem) % 2 != 0) 
                    return false;
            } 
            // For other remainders, the count of rem must equal the count of k - rem
            else if (!Objects.equals(remainderCount.get(rem), remainderCount.get(k - rem))) 
                return false;
        }

        return true;
    }
}