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