Abstract / Summary

Check if grouping all numbers into pairs makes each pair's sum divisible by a given integer.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 46% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Counting
• Hash Table

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether an array of integers can be partitioned into pairs whose sums are divisible by a given integer k. It does this by tracking the frequency of each remainder when the array elements are reduced modulo k. As each element is processed, the algorithm attempts to match it with a previously seen element that would complete a divisible-by-k pair. If every element finds a partner, the function returns True; otherwise it returns False.

Counting Modulo Frequencies

The first logical block creates a frequency container sized exactly to the divisor k. This container holds the count of elements that have been seen but not yet paired.

freq = [0] * k

By allocating a list of length k, the code guarantees constant-time access to any remainder bucket, which is essential for the subsequent pairing step.

Iterating Over the Input Array

The core of the algorithm is a single pass over the input list arr. For each element, the remainder with respect to k is computed, and the complementary remainder needed to reach a multiple of k is derived.

for a in arr:
    mod   = a % k
    other = k - mod if mod > 0 else 0

The expression a % k yields a non-negative remainder even when a is negative, ensuring that the remainder always falls within the range [0, k-1]. The complementary remainder other is calculated as k - mod for non-zero remainders; when mod is zero, the complement is also zero, reflecting the fact that two numbers both divisible by k form a valid pair.

Pairing Logic

After determining the needed complement, the algorithm checks whether an unpaired element with that complement already exists. If such an element is present, the pair is formed by decrementing the stored count; otherwise, the current element’s remainder is recorded as awaiting a future partner.

if freq[other] > 0:
    freq[other] -= 1
else:
    freq[mod] += 1

This conditional update ensures that each element is either immediately paired or stored for later matching, maintaining the invariant that freq always reflects the set of remainders that are still waiting for a partner.

Final Verification

When the loop finishes, the algorithm verifies that no unpaired remainders remain. This is done by summing the frequency list and checking that the total is zero.

return sum(freq) == 0

If every remainder count has been reduced to zero, every element found a partner, and the function returns True. Any leftover count indicates that at least one element could not be paired, resulting in False.

Edge Cases Handled

The implementation gracefully manages several special situations:

When an element is exactly divisible by k (mod equals zero), the complement is also zero. The code therefore pairs such elements with each other, correctly handling sequences of numbers that are multiples of k.

When k equals one, every integer yields a remainder of zero. The frequency list has a single slot, and the pairing logic reduces the count for each pair, ultimately confirming that any even-length array can be paired, while an odd-length array will leave a single remainder unpaired.

Negative numbers are accommodated because Python’s modulo operator returns a non-negative remainder for a positive divisor. Consequently, the remainder calculation and complement determination remain valid regardless of sign.

If the input array is empty, the frequency list remains all zeros, and the final sum check evaluates to True, correctly indicating that an empty set can trivially be considered fully paired.

Performance Optimizations

The algorithm achieves efficiency through several deliberate choices. By using a fixed-size list indexed by remainder values, it avoids the overhead of hash-based structures and ensures that each lookup and update occurs in constant time. The single traversal of the input array eliminates the need for nested loops, preventing quadratic behavior even for large inputs.

Storing only the count of unpaired remainders, rather than the actual elements, reduces memory usage to a size proportional to k. This compact representation allows the function to handle very large arrays without proportional growth in auxiliary storage.

The immediate pairing attempt (if freq[other] > 0) reduces the number of entries that remain in the frequency list, keeping the list sparse and minimizing the work required during the final summation. This early reduction of pending counts contributes to faster completion, especially when many complementary pairs are encountered early in the iteration.

Imagine a big box filled with numbered blocks. The goal is to see if every single block can find a matching partner so that when you add their numbers together, the total can be divided perfectly by another special number called k.

Inside the computer, a list called freq is created. Think of this list as a series of small cubbyholes where blocks wait to find their match. The code looks at each block one by one. For every block, it figures out its remainder when divided by k. This helps decide which cubbyhole the block belongs to while it looks for its partner.

If a friend is already waiting in the right cubbyhole, they hold hands and leave the game together to form a perfect pair. If nobody is there to match, the block sits in its own cubbyhole and waits for someone else to show up later. After checking every single block in the box, the code looks back at the cubbyholes. If every cubbyhole is completely empty, it means everyone found a perfect match.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java		Python				TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python	JS	Go	Rust	TS
	Progiez	C++	Java		Python
github	black-shadows	C++
	charles-wangkai		Java
	FelixFan1122			C#
	fsq	C++
	JoshCrozier					JS
	keineahnung2345	C++
	lkwq007				Python
	suxrobGM			C#
	varunu28		Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
FelixFan1122	C#
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
varunu28	Java
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality