Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Hashing & Two Pointers

Count Pairs with Difference K

Medium · Hashing & Two Pointers · Asked at Amazon, Microsoft, Goldman Sachs

Count the number of distinct value pairs (x, y) from the array with y − x = k. Each pair of values counts once, even if the values repeat.

Input

First line: n. Second line: n integers. Third line: k.

Output

The number of distinct pairs.

Constraints

Example 1

Input

5
1 5 3 4 2
3

Output

2

Example 2

Input

4
1 1 1 2
1

Output

1

Hints

  1. Repeated values don't create new pairs — work with the set of distinct values.
  2. For each distinct x, the pair exists exactly when x + k is also in the set.

Approach

Since k ≥ 1, a pair (x, x + k) is determined by its smaller value x. Put the values in a hash set and count the x for which x + k is also present. Each distinct pair is counted once, however many copies the array holds.

Complexity: O(n) average time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_set<long long> s;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        s.insert(x);
    }
    long long k;
    cin >> k;
    int count = 0;
    for (long long x : s)
        if (s.count(x + k)) count++;
    cout << count << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
s = set(data[1 : n + 1])
k = data[n + 1]
print(sum(1 for x in s if x + k in s))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Long> s = new HashSet<>();
        for (int i = 0; i < n; i++) s.add(sc.nextLong());
        long k = sc.nextLong();
        int count = 0;
        for (long x : s)
            if (s.contains(x + k)) count++;
        System.out.println(count);
    }
}

Solve Count Pairs with Difference K online · All practice problems