Is Check If Array Pairs Are Divisible by k easy or hard?

The problem is rated Medium on LeetCode. The implementation is straightforward once you recognize the remainder complement rule, but identifying that modular arithmetic insight is what makes it a typical medium-level interview question.

Check If Array Pairs Are Divisible by k Python/Java solution

Python and Java solutions typically use a dictionary or HashMap to track remainder frequencies. After counting remainders, iterate through the map to ensure every remainder r has a matching k - r frequency and handle special cases like remainder 0.

How to solve Check If Array Pairs Are Divisible by k in O(n)?

Compute num % k for every element and store frequencies in a hash map or array. For each remainder r, ensure its frequency matches the frequency of k - r. Handle edge cases where r = 0 (must be even count) and when r = k/2 if k is even. This single pass plus validation gives an O(n) solution.

What is the best approach for Check If Array Pairs Are Divisible by k?

The best approach uses hashing with remainder counting. Compute each element's remainder modulo k and store frequencies in a hash map. For a valid pairing, the count of remainder r must equal the count of k - r, and remainder 0 values must appear an even number of times. This approach runs in O(n) time with O(k) space.

Is Check If Array Pairs Are Divisible by k asked at Google/Amazon/Meta?

Variants of remainder pairing and modular arithmetic problems appear in interviews at companies like Amazon and Google. These companies often test hash map reasoning, complement matching, and array frequency techniques similar to this problem.

What data structure is used in Check If Array Pairs Are Divisible by k?

A hash table (or frequency array) stores counts of each remainder when elements are divided by k. This structure enables constant-time lookup to verify that each remainder has a matching complementary remainder.

What is the time complexity of Check If Array Pairs Are Divisible by k?

The optimal solution runs in O(n) time by scanning the array once and counting remainders in a hash map. Validation of remainder pairs takes O(k). The space complexity is O(k) because at most k remainder values are stored.

Description Hints 3 Solution Video 13:46

1497. Check If Array Pairs Are Divisible by k

Medium46.2% acceptance8 companies

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: