FastPrep
Problem · Array

Perfect Pairs

Learn this problem
● MediumSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

A pair of integers (x, y) is perfect if both of the following conditions are met:

  • min(|x - y|, |x + y|) ≤ min(|x|, |y|)
  • max(|x - y|, |x + y|) ≥ max(|x|, |y|)

Given an integer array arr of length n, find the number of perfect pairs (arr[i], arr[j]) where 0 ≤ i < j < n.

Here, min(a, b) and max(a, b) are the minimum and maximum of a and b, and |x| is the absolute value of x.

Complete getPerfectPairsCount with the following parameter:

  • int arr[n]: an array of integers

Returns: long, the number of perfect pairs.

Function

getPerfectPairsCount(arr: int[]) → long

Examples

Example 1

arr = [2, 5, 3]return = 2

The possible pairs are (2, 5), (2, 3), and (5, 3).

  • For (2, 5), min(3, 7) = 3 > min(2, 5) = 2, so the pair is not perfect.
  • For (2, 3), min(1, 5) = 1 ≤ 2 and max(1, 5) = 5 ≥ 3, so the pair is perfect.
  • For (5, 3), min(2, 8) = 2 ≤ 3 and max(2, 8) = 8 ≥ 5, so the pair is perfect.

Therefore, the answer is 2.

Constraints

  • 2 ≤ n ≤ 2 * 10^5
  • -10^9 ≤ arr[i] ≤ 10^9

More Snowflake problems

drafts saved locally
public long getPerfectPairsCount(int[] arr) {
    // write your code here
}
arr[2, 5, 3]
expected2
checking account