TABLE OF CONTENT |
---|

Problem : Pairs with difference of K |

How to approach the solution? |

Test Cases |

Solution in Java |

Solution in C++ |

Solution in Python |

## Problem : Pairs with difference of K

You are given an integer array and the number K. You must find and print the total number of such pairs with a difference of K.

Take the absolute difference between the array's elements.

### Format of Input:

```
The first line of input comprises an integer indicating the array's size. It will be denoted by the symbol n.
The following line contains n space-separated numbers indicating the array's elements' values.
The next line provides an integer indicating the value of K.
```

### Format of Output:

`The output's first and only line contains a count of all pairs with an absolute difference of K.`

### Constraints :

```
0 <= n <= 10^4
Time Limit: 1 sec
```

#### Sample Input 1 :

```
4
5 1 2 4
3
```

#### Sample Output 1 :

`2`

#### Sample Input 2 :

```
4
4 4 4 4
0
```

#### Sample Output 2 :

`6`

## How to approach the solution?

The naive approach to this problem would be to run a double nested loop and check every pair for their absolute difference. If it’s equal to ‘k’, we print it else we move to the next iteration.

The double nested loop will look like this:

```
for(i <- 0; i < arr.size() - 1; i <- i + 1):
for(j <- i + 1; j < arr.size(); j <- j + 1):
if(absolute difference of arr[i] and arr[k] is equal to k):
printPair();
```

The time complexity of this method is O(n^{2}) because of the double nested loop and the space complexity is O(1) since we are not using any extra space.

We can improve the time complexity to O(n) at the cost of some extra space.

The idea is that in the naive approach, we are checking every possible pair that can be formed but we don’t have to do that.

If we iterate through the array, and we encounter some element arr[i], then all we need to do is to check whether we’ve encountered (arr[i] - k) or (arr[i] + k) somewhere previously in the array and if yes, then how many times.

Ideally, we would want to access this information in O(1) time. For this, we can use a HashMap.

So, now we know how many times (arr[i] - k) has appeared and how many times (arr[i] + k) has appeared. Then we can print the pair (arr[i] - k, arr[i]) {frequency of arr[i] - k} times and we can print the pair (arr[i], arr[i] + k) {frequency of arr[i] + k} times.

**We also need to look out for a few things -**

Think about what will happen if k is 0. Then (arr[i] + k) will be equal to (arr[i] - k) and we will print our pairs twice! Obviously we don’t want that to happen. So we need to add an extra check for this special case.

**The pseudo-code for this approach -**

```
function pairsWithDifferenceK(arr,k):
HashMap(integer,integer) frequencyMap
for element in arr:
a <- element - k
b <- element + k
if(frequencyMap contains the key ‘a’):
//print pair frequencyMap[a] times
if(k != 0 and frequencyMap contains the key ‘b’):
//print pair frequencyMap[b] times
//frequencyMap[element] is initially 0
frequencyMap[element] <- frequencyMap[element] + 1
```

**Test Cases :** Pairs with difference of K

#### Input - Test Case #1

`4`

5 1 2 4

3

#### Input - Test Case #2

`4`

4 4 4 4

0

#### Input - Test Case #3

`4`

2 4 6 8

2

#### Output - Test Case #1

`2`

#### Output - Test Case #2

`6`

#### Output - Test Case #3

`3`

**Solution in Java : **Pairs with difference of K

We create a package named * PairsWithDiffK*. Inside the package we create two class files named

*Main.java*and

*Solution.java*.

In file ** Main.java** we write our main method -

package PairsWithDiffK; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));; static StringTokenizer st; public static void main(String[] args) throws NumberFormatException, IOException { st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int arr[] = new int[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken()); } int k = Integer.parseInt(br.readLine()); System.out.println(Solution.getPairsWithDifferenceK(arr, k)); } }

In file * Solution.java*, we write our solution for Java -

package PairsWithDiffK; import java.util.HashMap; public class Solution { public static int getPairsWithDifferenceK(int arr[], int k) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int pairCount = 0; for(int i : arr){ int p1 = i + k; boolean flag = false; if(i == p1) { flag = true; } if(map.containsKey(p1)){ pairCount += map.get(p1); } int p2 = i - k; if(map.containsKey(p2) && !flag){ pairCount += map.get(p2); } if(map.containsKey(i)){ map.put(i, map.get(i) + 1); } else{ map.put(i, 1); } } return pairCount; } }

## **Solution in C++ : **Pairs with difference of K

We create a folder named "* PairsWithDiffK*". Inside this folder we create two files named

*Main.cpp*and

*PairsWithDifferenceK.h*

Inside file ** Main.cpp** we write our C++ main method for this problem.

#include <iostream> using namespace std; #include "PairsWithDifferenceK.h" int main() { int n; cin >> n; int *input = new int[n]; for (int i = 0; i < n; i++) { cin >> input[i]; } int k; cin >> k; cout << getPairsWithDifferenceK(input, n, k); delete[] input; }

Inside file ** PairsWithDifferenceK.h** we write our C++ solution.

#include <unordered_map> int getPairsWithDifferenceK(int *arr, int n, int k) { unordered_map<int, int> freq; int pairCount = 0; for (int i = 0; i < n; ++i) { int complement = arr[i] + k; pairCount += freq[complement]; if (k != 0) { complement = arr[i] - k; pairCount += freq[complement]; } ++freq[arr[i]]; } return pairCount; }

## **Solution in Python : **Pairs with difference of K

Inside file ** PairsWithDiffK.py** we write our Python solution to this problem.

def printPairDiffK(l, k): pairCount=0 m = {} for num in l: if num+k in m: pairCount += m[num+k] if k!=0 and num-k in m: pairCount += m[num-k] # Update map if num in m: m[num] += 1 else: m[num] = 1 return pairCount #Main method n=int (input()) l=list(int(i) for i in input().strip().split(' ')) k=int (input()) print(printPairDiffK(l, k))

Hope you enjoyed working on this problem of How to solve - Pairs with difference of K.

### You may like to Explore -

**How to solve Find the Character Case Problem – Java, Python, C , C++**

**An example of a Simple Calculator in Java Programming**

**Othello Move Function – Java Code Problem Solution**

Cheers!

Happy Coding.

About the AuthorThis article was authored byRawnak.

Comments are closed.