Perfect Pair Count
MediumMath · SalesForce
Call two integers x and y a perfect pair if both of these hold:
min(|x - y|, |x + y|) <= min(|x|, |y|)max(|x - y|, |x + y|) >= max(|x|, |y|)
Given a list values, count the pairs of indices (i, j) with i < j such that values[i] and values[j] form a perfect pair. Pairs are counted by index, so equal values at different positions are different pairs.
The list can be large, so checking every pair directly is too slow. Simplify the condition first.
Example 1
- Input:
- values = [3, -5, 8, 2]
- Output:
- 3
- Explanation
- Take
-5and8:|x - y| = 13and|x + y| = 3. The smaller, 3, is at mostmin(5, 8) = 5, and the larger, 13, is at leastmax(5, 8) = 8, so it is perfect. The perfect pairs are(3, -5),(3, 2)and(-5, 8); for(3, 8)the smaller quantity is 5, which exceeds 3.
Example 2
- Input:
- values = [1, 2, -2, 4]
- Output:
- 5
- Explanation
- Every pair is perfect except
(1, 4), wheremin(3, 5) = 3is larger thanmin(1, 4) = 1. That leaves 5 of the 6 pairs.
Example 3
- Input:
- values = [0, 0, 1]
- Output:
- 1
- Explanation
- The two zeros form a perfect pair because every quantity is 0. Pairing a zero with
1fails the first condition, since1 > 0.
Constraints
- 0 ≤
values.length≤ 105 - -109 ≤
values[i]≤ 109