0997MediumArrayHash TableCounting

Pairing Meter Readings Into Whole Cycles

Tracked in this browser only

Trains the technique from

LeetCode 1497Check If Array Pairs Are Divisible by k

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A meter log holds an even count of readings in readings, and one full cycle of the meter spans k units.

Return whether the readings can be split into pairs, every reading used in exactly one pair, so that each pair's two readings add up to a whole number of cycles.

Examples

Example 1

Input: readings = [2, 3, 5, 7, 8, 15], k = 5
Output: true

Leaving 5 with 15 gives a pair adding to two whole cycles. That leaves 2 with 8 and 3 with 7, each adding to one cycle.

Example 2

Input: readings = [1, 1], k = 5
Output: false

Both readings leave one over, and one plus one is not a whole cycle, so the only possible pair fails.

Example 3

Input: readings = [-1, 1], k = 5
Output: true

The negative reading leaves four over against the cycle, which completes the cycle with the one left over by the other reading.

Constraints

readings.length is even.
2 <= readings.length <= 10^5
-10^9 <= readings[i] <= 10^9
1 <= k <= 10^5

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def can_arrange(readings: list[int], k: int) -> bool:

Java

public boolean canArrange(int[] readings, int k)

The intended approach

Time O(n + k) for n readings and a cycle length of k.Space O(k) for the tallies.

Only what each reading leaves over against the cycle length matters. Two readings add to a whole number of cycles exactly when their leftovers add to the cycle length, or when both leave nothing over. Take leftovers that always land from zero up to one below the cycle length, so a negative reading behaves like any other. Tally how many readings sit on each leftover. Readings leaving nothing over can only pair with each other, so that tally has to be even. When the cycle length is even, the halfway leftover also pairs only with itself, so its tally has to be even too. Every other leftover pairs with the one that completes a cycle, so those two tallies have to match exactly. Those conditions are enough as well as necessary, because they describe a pairing that uses every reading once. Worth noting: with an even count of readings, the matched pairs account for an even amount between them, so the two self-pairing tallies always share the same evenness. Checking one of them therefore settles the other; both are checked below only to keep the reasoning in plain sight.

Pythonentry point: can_arrange

def can_arrange(readings, k):
    tally = [0] * k
    for value in readings:
        tally[value % k] += 1
    if tally[0] % 2:
        return False
    if k % 2 == 0 and tally[k // 2] % 2:
        return False
    for left in range(1, (k + 1) // 2):
        if tally[left] != tally[k - left]:
            return False
    return True

The obvious version

Pair the readings off outright. Reduce each to its leftover and sort them, then take each unpaired leftover in turn and hunt the rest for one that completes the cycle with it, marking both used. Report failure at the first leftover with nowhere to go. Since readings on the same leftover are interchangeable, taking the first partner found is safe. Costs a hunt per reading rather than a tally per leftover.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_can_arrange(readings, k):
    left = sorted(value % k for value in readings)
    used = [False] * len(left)
    for i in range(len(left)):
        if used[i]:
            continue
        want = (k - left[i]) % k
        found = -1
        for j in range(i + 1, len(left)):
            if not used[j] and left[j] == want:
                found = j
                break
        if found < 0:
            return False
        used[i] = True
        used[found] = True
    return True

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in