Count perfect pairs

Problem A pair of integers (x, y) is perfect if both conditions hold: min(|x−y|, |x+y|) <= min(|x|, |y|) and max(|x−y|, |x+y|) >= max(|x|, |y|). Given an integer array arr of length n, count the number of perfect pairs (arr[i], arr[j]) with 0 <= i < j < n.

Input / Output

• Input: int arr[n] — an array of integers (values may be negative).
• Output: long — the number of perfect pairs. The count can reach ~n²/2, which overflows a 32-bit int.

Constraints

• 2 <= n <= 10^5
• Values may be negative; take care that abs(INT_MIN) overflows in most languages — widen before taking the absolute value.

Example

• arr = [2, 5, −3] → 2. (2, 5) fails: min(|2−5|, |2+5|) = 3 > min(2, 5) = 2. (2, −3) passes: min(5, 1) = 1 <= 2 and max(5, 1) = 5 >= 3. (5, −3) passes: min(8, 2) = 2 <= 3 and max(8, 2) = 8 >= 5.

Expected approach

• Key identity: for any x, y, min(|x−y|, |x+y|) = ||x| − |y|| and max(|x−y|, |x+y|) = |x| + |y|. So with a = min(|x|, |y|) and b = max(|x|, |y|), condition 2 (a + b >= b) is always true, and condition 1 reduces to b − a <= a, i.e. b <= 2a.
• Therefore a pair is perfect iff max(|x|, |y|) <= 2 · min(|x|, |y|): only magnitudes matter, and order/sign are irrelevant.
• Take absolute values, sort ascending, then for each index i count indices j > i with v[j] <= 2·v[i] using a forward-moving two-pointer (or binary search). The pointer never moves backward, so counting is O(n) after the sort.
• Complexity: O(n log n) time for the sort, O(n) extra space (or in-place).