×

# 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(n2), 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