1193MediumArrayMathTwo PointersSorting

Dial Settings That Agree

Tracked in this browser only

Trains the technique from

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 bench of dials has been trimmed, trims[i] being the trim on the i-th dial. A trim may be negative.

Two trims a and b agree when both of these hold:

the smaller of |a - b| and |a + b| is no more than the smaller of |a| and |b|;
the larger of |a - b| and |a + b| is no less than the larger of |a| and |b|.

Return the number of pairs of positions i < j whose trims agree.

Examples

Example 1

Input: trims = [4, 7, 9, 2]
Output: 3

Magnitudes 2, 4, 7 and 9. The pairs that agree are 2 with 4, 4 with 7, and 7 with 9, since each larger magnitude is within double the smaller. 2 with 7, 2 with 9 and 4 with 9 all miss.

Example 2

Input: trims = [-8, 4, -4, 8]
Output: 6

Signs fall away, leaving magnitudes 8, 4, 4 and 8. Since 8 is exactly double 4, and equal magnitudes always agree, all six pairs on the bench agree.

Example 3

Input: trims = [0, 3]
Output: 0

The smaller of the two differences is 3 and the smaller magnitude is 0, so the first test fails and the only pair on the bench does not agree.

Constraints

2 <= trims.length <= 10^5
-10^9 <= trims[i] <= 10^9

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 perfect_pairs(trims: list[int]) -> int:

Java

public long perfectPairs(int[] trims)

The intended approach

Time O(n log n) for the sort, then one sweep.Space O(n) for the sorted magnitudes.

Both tests collapse. Write `x` for the smaller of `|a|` and `|b|` and `y` for the larger. If the two trims carry the same sign then `|a - b|` is `y - x` and `|a + b|` is `x + y`; if they carry opposite signs the two swap places. Either way the pair `|a - b|`, `|a + b|` is the pair `y - x`, `x + y`, so the smaller of them is always `y - x` and the larger is always `x + y`. The second test then reads `x + y >= y`, which is `x >= 0` and so holds for every pair, and the first reads `y - x <= x`. So two trims agree exactly when the larger magnitude is at most twice the smaller, and the signs never matter at all. Take magnitudes and sort them. Walking the sorted magnitudes with `i`, the dials that agree with it are those sitting at or before the last position holding at most `2 * sizes[i]`. That last position only moves forward as `i` moves forward, because `sizes[i]` never falls, so one pointer sweeping forward once finds it for every `i`. Counting only the positions after `i` keeps each pair counted once. The tally can pass what a 32-bit integer holds, so it wants a wide type.

Pythonentry point: perfect_pairs

def perfect_pairs(trims):
    sizes = sorted(abs(trim) for trim in trims)
    n = len(sizes)
    total = 0
    reach = 0
    for i in range(n):
        if reach < i:
            reach = i
        while reach + 1 < n and sizes[reach + 1] <= 2 * sizes[i]:
            reach += 1
        total += reach - i
    return total

The obvious version

Read the two tests off the page for every pair. For each `i < j`, work out `|a - b|` and `|a + b|`, take the smaller and larger of those two and the smaller and larger of `|a|` and `|b|`, and count the pair when both tests hold. Costs a pass over every pair with no reasoning applied.

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_perfect_pairs(trims):
    n = len(trims)
    total = 0
    for i in range(n):
        for j in range(i + 1, n):
            a = trims[i]
            b = trims[j]
            gap = abs(a - b)
            joint = abs(a + b)
            lo = gap if gap < joint else joint
            hi = gap if gap > joint else joint
            small = abs(a) if abs(a) < abs(b) else abs(b)
            large = abs(a) if abs(a) > abs(b) else abs(b)
            if lo <= small and hi >= large:
                total += 1
    return total

How this problem was checked

Reference solution executed against 16 test cases — 16 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