• Posts

Problem 1497 Check If Array Pairs Are Divisible by k

Problem Statement

Link - Problem 1497

Question

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

Solution

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        unordered_map<int, int> remainderCount;

        for (int num : arr) {
            int remainder = ((num % k) + k) % k; // This is to get a non negetive reminder
            remainderCount[remainder]++;
        }

        for (auto& pair : remainderCount) {
            int remainder = pair.first;
            int count = pair.second;

            if (remainder == 0) {
                // For remainder 0, there must be an even number of elements
                if (count % 2 != 0) {
                    return false;
                }
            } else if (remainder * 2 == k) {
                // For remainder k/2, there must be an even number of elements
                if (count % 2 != 0) {
                    return false;
                }
            } else {
                // For other remainders, there must be a matching count of k - remainder
                int complement = k - remainder;
                if (remainderCount[complement] != count) {
                    return false;
                }
            }
        }

        return true;
    }
};

Complexity Analysis

| Algorithm  | Time Complexity | Space Complexity |
| ---------- | --------------- | ---------------- |
| Hash Table | O(n)            | O(k)             |

Explanation

Intial Thoughts

To approach this problem, we should first consider how the array can be divided into pairs such that the sum of each pair is divisible by k. We can think of this as finding pairs of numbers that ‘complement’ each other with respect to k. It’s also important to think about how the remainders of the numbers when divided by k can help us find these pairs. We should consider how many numbers in the array have each possible remainder when divided by k, and how these counts can be used to determine if the desired pairs can be formed.

Intuitive Analysis

Intuitively, we can solve this problem by considering the counts of each remainder when the numbers in the array are divided by k. We should think about how the counts of each remainder can be used to determine if there are enough ‘matching’ numbers to form the desired pairs. For example, if we have a certain number of elements with a remainder of r when divided by k, we need to have the same number of elements with a remainder of k - r. We should also consider the special cases where the remainder is 0 or k/2, as these may require an even number of elements. By thinking about these cases and how the counts of each remainder relate to each other, we can develop a solution to the problem.

1. Intuition

• The problem requires dividing the array into pairs such that the sum of each pair is divisible by k, which suggests using the concept of remainders when dividing by k.
• To ensure the sum of each pair is divisible by k, the remainders of the two numbers in each pair must add up to k.
• We can use a hashmap to store the count of each remainder, which allows us to efficiently check if there’s a matching count of k - remainder for each remainder.
• For remainder 0, there must be an even number of elements because the sum of two numbers with remainder 0 is always divisible by k.
• For remainder k/2, there must also be an even number of elements because the sum of two numbers with remainder k/2 is always divisible by k.
• The solution works by iterating through the array, calculating the remainder of each number, and updating the count in the hashmap, then checking if the counts satisfy the conditions for each remainder.
• This approach ensures that we can find a way to divide the array into pairs with sums divisible by k if it’s possible, and it does so efficiently by avoiding unnecessary iterations and comparisons.

2. Implementation

• We use an unordered_map called remainderCount to store the count of each remainder, where the key is the remainder and the value is the count.
• We iterate through the array using a for loop, and for each number, we calculate its remainder using the expression ((num % k) + k) % k to ensure a non-negative remainder.
• We then update the count in the remainderCount hashmap using remainderCount[remainder]++.
• After iterating through the array, we iterate through the remainderCount hashmap using a for loop, and for each remainder, we check if the count satisfies the conditions.
• For remainder 0 and k/2, we check if the count is even using count % 2 != 0, and if not, we return false.
• For other remainders, we check if there’s a matching count of k - remainder using remainderCount[complement] != count, and if not, we return false.
• If we pass all the checks, we return true, indicating that we can divide the array into pairs with sums divisible by k.

Complexity Analysis

Time Complexity:

• The time complexity of the given solution is O(n), where n is the number of elements in the input array. This is because the solution iterates through the array twice: once to calculate the remainder of each number and store it in the remainderCount hash table, and once to check the counts of remainders and their complements.
• The dominant operations are the iterations through the array and the hash table lookups. Since these operations are performed a constant number of times for each element in the array, the time complexity is linear.
• The Big O classification of O(n) is justified because the time taken by the algorithm grows linearly with the size of the input array. In the worst, average, and best cases, the time complexity remains O(n) because the algorithm always iterates through the entire array.

Space Complexity:

• The space complexity of the given solution is O(k), where k is the input integer. This is because the solution uses a hash table remainderCount to store the counts of remainders, and in the worst case, there can be k distinct remainders.
• The impact of the data structure is that the hash table can store up to k elements, each corresponding to a remainder. This means that the memory usage grows linearly with k.
• The space complexity of O(k) is justified because the size of the hash table grows linearly with k. In this case, the space complexity does not depend on the size of the input array, but rather on the input integer k.

Footnote

This question is rated as Medium difficulty.

Hints

Keep an array of the frequencies of ((x % k) + k) % k for each x in arr.

for each i in [0, k - 1] we need to check if freq[i] == freq[k - i]

Take care of the case when i == k - i and when i == 0

Similar Questions: