Overview

This problem asks us to count the number of pairs formed by selecting 2 integers from \(N\) integers such that the absolute difference is exactly \(K\).

Analysis

Key Insight

An absolute difference of \(K\) means that for two numbers \(a\) and \(b\), \(|a - b| = K\) must hold. This means one of the following two cases: - \(b = a + K\) (\(b\) is \(K\) larger than \(a\)) - \(b = a - K\) (\(b\) is \(K\) smaller than \(a\))

Problem with the Naive Approach

The method of enumerating all pairs and checking their differences has a time complexity of \(O(N^2)\). When \(N\) is at most \(2 \times 10^5\), this requires approximately \(4 \times 10^{10}\) operations, which will result in TLE (Time Limit Exceeded).

Solution

For each element \(a\), we need to efficiently check whether the value \(a + K\) exists in the sequence. Using a hash table (Counter or dict in Python), existence checks can be performed in \(O(1)\).

Important Point: When considering a pair of \(a\) and \(a + K\), the pair of \(a + K\) and \(a\) is the same. Therefore, by only searching for “elements that are \(K\) larger than itself” for each element, we prevent counting the same pair twice.

Concrete Example

Input: \(N = 5\), \(K = 2\), \(A = [1, 3, 5, 3, 7]\)

Counting the occurrences of each element: - \(1\): 1 time - \(3\): 2 times - \(5\): 1 time - \(7\): 1 time

Finding pairs with difference \(2\): - For \(1\), \(1 + 2 = 3\) exists → \(1 \times 2 = 2\) pairs - For \(3\), \(3 + 2 = 5\) exists → \(2 \times 1 = 2\) pairs - For \(5\), \(5 + 2 = 7\) exists → \(1 \times 1 = 1\) pair - For \(7\), \(7 + 2 = 9\) does not exist → \(0\) pairs

Total: \(2 + 2 + 1 = 5\) pairs

Algorithm

1. Count the occurrences of each element in the sequence using Counter
2. For each unique value \(a\) in the Counter:
   • Check if \(a + K\) exists in the Counter
   • If it exists, add (count of \(a\)) × (count of \(a + K\)) to the pair count
3. Output the total pair count

Complexity

• Time Complexity: \(O(N)\)
  • Building the Counter takes \(O(N)\)
  • The loop over each unique value runs at most \(N\) times, with each iteration being \(O(1)\)
• Space Complexity: \(O(N)\)
  • The Counter may have up to \(N\) keys

Implementation Notes

• Using Counter allows for concise management of occurrence counts for each value

• By only searching for \(a + K\) instead of \(a - K\), we prevent duplicate counting of pairs

• When the same value appears multiple times (e.g., \(3\) appears twice), we take the product of occurrence counts to correctly count all combinations

  Source Code

from collections import Counter

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    count = Counter(A)
    result = 0
    
    for a in count:
        # Check if a + K exists
        if a + K in count:
            result += count[a] * count[a + K]
    
    print(result)

solve()

---

This editorial was generated by claude4.5opus.