Pair Up Into Multiples

Medium

You are given an integer array values of even length and an integer divisor. Split all the elements into pairs (each element in exactly one pair) so that the sum of every pair is a multiple of divisor. Return True if such a split exists, and False otherwise.

Example 1

values=[7, 2, 9, 4, 1, 1], divisor=4 → False

The remainders mod 4 are 3, 2, 1, 0, 1, 1. Remainder 2 and remainder 0 each appear once, so they have no partner.

Example 2

values=[5, -2, 8, 1, 3, 10], divisor=3 → False

The remainders mod 3 are 2, 1, 2, 1, 0, 1. There is a single value with remainder 0, so it has no partner.

Example 3

values=[6, 14, -3, 3], divisor=10 → True

(6, 14) sums to 20 and (-3, 3) sums to 0; both are multiples of 10.

Constraints

2 ≤ len(values) ≤ 10⁵, and the length is even
-10⁹ ≤ values[i] ≤ 10⁹
1 ≤ divisor ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Counting

Similar problems

More Than a Third of the Votes Medium Most Common Values Medium Jobs With a Cooldown Medium Most Searched Words Medium Domain Visit Rollup Medium

Input

values=[7, 2, 9, 4, 1, 1], divisor=4

Expected

False

Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.