#1497

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Check If Array Pairs Are Divisible by k

Check if array pairs are divisible by k by pairing elements whose sums are divisible by k using array scanning and hash lookup.

array hash table counting

Problem Statement

Given an array of integers arr of even length n and an integer k, you need to determine if it's possible to divide the array into n / 2 pairs such that the sum of each pair is divisible by k. If such a division exists, return true; otherwise, return false.

To solve the problem, consider the remainders when elements are divided by k. Group elements with the same remainder, and check if complementary remainders (e.g., remainder r and k-r) can form valid pairs. The complexity arises from efficiently counting the frequencies of remainders and matching them properly.

Examples

Example 1

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5

Output: true

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

Pairs are (1,6),(2,5) and(3,4).

Example 3

Input: arr = [1,2,3,4,5,6], k = 10

Output: false

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 Approach

Array Scanning

Iterate through the array and calculate the remainder of each element when divided by k. Store the frequency of each remainder in a hash table. This step ensures that each element's remainder is tracked efficiently.

Pairing Remainders

For each element in the array, check if there is a complementary element with a remainder such that their sum is divisible by k. If the remainder is 0, there must be an even count of such elements. For other remainders, the count of an element with remainder r must match the count of elements with remainder k-r.

Hash Table Lookup

Using the hash table to count frequencies of remainders, perform efficient lookups to verify if each element can be paired with an element that complements it. The hash table ensures that the solution runs in linear time while managing the pairing logic.

Complexity Analysis

Metric	Value
Time	O(n \cdot \log n)
Space	O(n)

The time complexity is O(n log n) due to sorting the array for remainder calculation and pairing. Space complexity is O(n) because we store the frequency of each remainder in a hash table. Optimizations in frequency matching help reduce unnecessary comparisons, making this approach efficient even for large input sizes.

What Interviewers Usually Probe

Candidate understands the use of hash tables for frequency counting and efficient lookups.
Candidate demonstrates familiarity with modular arithmetic and the concept of remainders when working with divisibility conditions.
Candidate can optimize a solution by using a hash table to match complementary remainders efficiently.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for elements with a remainder of 0, which require an even count of such elements to form valid pairs.
Overlooking the case where the remainder of an element is larger than half of k, leading to mismatched pairs.
Assuming that elements with the same remainder can always pair together, without checking if their frequencies align properly.

Follow-up variants

What if the array has an odd length? The problem could become unsolvable since we need an even number of elements to form pairs.
Instead of checking divisibility by a constant k, what if the condition were a variable, such as prime numbers? The approach still works with slight modifications to the remainder check.
What if the problem only allowed certain ranges of numbers (e.g., only positive numbers)? The solution could be simplified since remainders would be restricted to a smaller range.

FAQ

How do I handle cases where the array's length is odd?

In this problem, the array length is guaranteed to be even. If it were odd, pairing elements would be impossible, and the answer would always be false.

Why is the time complexity O(n log n)?

The primary complexity arises from sorting the array to calculate remainders, followed by hash table operations for pairing. Sorting the array adds O(n log n) time complexity.

What is the significance of k in this problem?

The value of k is used to calculate the remainders of array elements. The main goal is to check if pairs of elements can be formed such that their sums are divisible by k.

Can the hash table be optimized further?

The current approach using a hash table to store frequencies is already optimal in terms of space and time complexity for this problem.

What if I want to solve this problem without using a hash table?

Without a hash table, the problem would require nested loops or additional data structures to track remainders, which would increase the time complexity to O(n^2), making it less efficient.

terminal

Solution

Solution 1: Counting Remainders

The sum of two numbers $a$ and $b$ is divisible by $k$ if and only if the sum of their remainders when divided by $k$ is divisible by $k$.

1

2

3

4

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        cnt = Counter(x % k for x in arr)
        return cnt[0] % 2 == 0 and all(cnt[i] == cnt[k - i] for i in range(1, k))

Continue Practicing

#1512 number of good pairs #1481 least number of unique integers after k removals #1394 find lucky integer in an array