Home » Data Structure » Array Data Structure

Count all distinct pairs with difference equal to k

C++ implementation to count all distinct pairs with difference equal to k.
Submitted by Vikneshwar GK, on February 08, 2022

Consider an integer array of size n and a positive integer k. The task at hand is to find the number of distinct pairs in the array whose difference is equal to k.

Example:

Input:
array= {5, 2, 4, 8, 3}
k = 3

Output:
Number of pairs whose difference is equal to k: 2

Explanation:
The pair (5, 2) and (8, 5) has a difference equal to 3.
Therefore count is 2.

Input:
array= {3, 9, 8, 2, 5}
k = 6

Output:
Number of pairs whose difference is equal to k: 2

Explanation: 
The pair (3, 9) and (8, 2) has a difference equal to 6.
Therefore count is 2.

Solution 1: Brute force

This is the inefficient method, that is, to try out every possible combination and check the difference is equal to k.

Iterate through the array using a nested loop, where the outer loop selects one element whereas the inner loop picks another element
If the difference of these elements is k, then increment the counter
Print the counter

Note: This method is suitable only for the array that contains distinct elements.

C++ Implementation:

#include <iostream>
using namespace std;

// Function to count the pairs
// whose difference is k
int pairCount(int array[], int length, int k)
{
    int count = 0;

    // Iterate through the array
    for (int i = 0; i < length; i++) {
        for (int j = i + 1; j < length; j++)
            // find difference and check whether it equals to k
            if (array[i] - array[j] == k || array[j] - array[i] == k)
                count++;
    }
    return count;
}

// main function
int main()
{
    int array[100], N, k;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    
    cout << "Enter k: ";
    cin >> k;
    cout << "Number of pairs whose difference is equal to k: " << pairCount(array, N, k);
    
    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:4
Enter element 2:2
Enter element 3:1
Enter element 4:7
Enter element 5:5
Enter k: 5
Number of pairs whose difference is equal to k: 1

Time Complexity: O(n²), where n is the length of the array

Solution 2: Using Sort

This is a comparatively efficient method that involves sorting the array first using a O(nlog(n)) algorithm. The idea here is to select one element and find its appropriate pair using binary search. It involves following steps:

Ascendingly sort the array
Iterate through the array and for each element array[i], find whether array[i]+k is present in the array by performing a binary search from i+1 to n–1
If found, increment the counter
Print the counter

C++ implementation:

#include <iostream>
#include <algorithm>
using namespace std;

// Function to perform binary search
int binarySearch(int array[], int low, int high, int element)
{
    if (high >= low) {
        int mid = low + (high - low) / 2;
        if (element == array[mid])
            return mid;
        if (element > array[mid])
            return binarySearch(array, (mid + 1), high, element);
        else
            return binarySearch(array, low, (mid - 1), element);
    }
    return -1;
}

// Function to count the pairs
// whose difference is k
int pairCount(int array[], int length, int k)
{
    int count = 0, i;

    // Sort the array
    sort(array, array + length);

    // Pick a first element point
    for (i = 0; i < length - 1; i++)
        if (binarySearch(array, i + 1, length - 1, array[i] + k) != -1)
            count++;

    return count;
}

// main function
int main()
{
    int array[100], N, k;

    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    cout << "Enter k: ";
    cin >> k;
    cout << "Number of pairs whose difference is equal to k: " << pairCount(array, N, k);

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:1
Enter element 2:5
Enter element 3:3
Enter element 4:4
Enter element 5:2
Enter k: 3
Number of pairs whose difference is equal to k: 2

Time Complexity: O(nlog(n)), where n is the length of the array

Solution 3: Using Hashing

In this approach, we will use hashing which will bring down the time complexity to O(n) in most cases. It involves the following steps:

Iterate through the array and insert the distinct elements into the hash map
Then check if array[i]+k is present in the hash map, if present, then increment the counter
Check if array[i]-k is present in the hash map, if present, then increment the counter
Remove array[i] from the table
Print the counter

C++ Implementation:

#include <iostream>
#include <algorithm>
using namespace std;

// Function to count the pairs
// whose difference is k
#define MAX 100000
int pairCount(int array[], int length, int k)
{
    // Initialize count
    int count = 0;

    // Declare hashmap
    bool hashmap[MAX] = { false };

    // Insert array elements to hashmap
    for (int i = 0; i < length; i++)
        hashmap[array[i]] = true;

    for (int i = 0; i < length; i++) {
        int element = array[i];
        if (element - k >= 0 && hashmap[element - k])
            count++;
        if (element + k < MAX && hashmap[element + k])
            count++;
        hashmap[element] = false;
    }
    return count;
}

// main function
int main()
{
    int array[100], N, k;

    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    cout << "Enter k: ";
    cin >> k;
    cout << "Number of pairs whose difference is equal to k: " << pairCount(array, N, k);

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:1
Enter element 2:5
Enter element 3:3
Enter element 4:2
Enter element 5:4
Enter k: 3
Number of pairs whose difference is equal to k: 2

Time Complexity: O(n), where n is the length of the array

Solution 4: Using Pointers

This approach involves using two pointers, namely left and right, each indicating the pair elements. It involves the following steps:

Sort the array
Both pointers point to the first element in the array
Find the difference between these elements
If the difference is k, then increment the counter and increment both left and right
If the difference is greater than k, then increment left
If the difference is lesser than r, then increment right
Print the counter

C++ Implementation:

#include <iostream>
#include <algorithm>
using namespace std;

// Function to count the pairs
// whose difference is k
int pairCount(int array[], int length, int k)
{
    int count = 0;

    // Sort array elements
    sort(array, array + length);

    int left = 0;
    int right = 0;
    while (right < length) {
        if (array[right] - array[left] == k) {
            count++;
            left++;
            right++;
        }
        else if (array[right] - array[left] > k)
            left++;
        else
            right++;
    }
    return count;
}

// main function
int main()
{
    int array[100], N, k;

    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    cout << "Enter k: ";
    cin >> k;
    cout << "Number of pairs whose difference is equal to k: " << pairCount(array, N, k);

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:1
Enter element 2:5
Enter element 3:3
Enter element 4:2
Enter element 5:4
Enter k: 3
Number of pairs whose difference is equal to k: 2

Time Complexity: O(nlog(n)), where n is the length of the array