# Count Pairs of Numbers with a Given Difference K

Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n. Return count of such pairs.

Example k=4 and a[]={7,623,19,10,11,9,3,15}
Output should be : 6
Pairs can be:
7,11
7,3
6,10
19,23
15,19
15,11

Solution:

```#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 1000000
int cmpfunc (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int main() {
// Enter your code here. Read input from STDIN. Print output to STDOUT /
int n,k;
int *a;
int count = 0;
int i;

scanf("%d %d", &n,&k);
a = malloc(n* sizeof(*a));
for(i=0; i<n;i++){
scanf("%d",&a[i]);
}
qsort(a, n, sizeof(int), cmpfunc);
int l = 0;
int r = 0;
while(r < n)
{
if(a[r] - a[l] == k)
{
count++;
l++;
r++;
}
else if(a[r] - a[l] > k)
l++;
else
r++;
}
printf("%d",count);
return 0;
}
```

Time Complexity: O(NLogN)
Space Complexity: O(1)

### 0 Thoughts on “Count Pairs of Numbers with a Given Difference K”

1. Great article…. Thanks

2. Arpan Chakarvarty on February 26, 2015 at 11:12 am said:

import java.util.HashMap;

public class SubtractionPair {

public static void printPair(int a[],int subValue)
{
HashMap store=new HashMap();
for(int i=0;i<a.length;i++)
{
store.put(a[i],1);
}
for(int i=0;i<a.length;i++)
{
if(store.containsKey(a[i]-subValue))
{
System.out.println("("+a[i]+","+(a[i]-subValue)+")");
}
if(store.containsKey(a[i]+subValue))
{
System.out.println("("+a[i]+","+(a[i]+subValue)+")");
}
store.remove(a[i]);
}

}

public static void main(String[] args) {

int a[]={7,6,23,19,10,11,9,3,15};
printPair(a,4);

}

}

4. RaghuNathan on March 3, 2015 at 11:46 pm said:

I Sorted the array before continuing. I used quick sort.This is just the idea & not the entire code . I looping the array from the end.
say if the origin list is a[]={7,623,19,10,11,9,3,15}
then after applying sort technique the list will be a[]={3,6,7,9,10,11,15,19,23}
number = 4;
Loop (End -> Start){
n = End;
if((a[n] – a[n-1]) == number){
if(a[n-2]){
if((a[n]-a[n-2])){
//pair found;
}
}
else if ((a[n] – a[n-1] ) < number){
//pair found;
}

}

n–;

}

5. Londani Mamathuba on April 27, 2015 at 1:34 am said:

Good day,Do you mind creating a function where you do not have to sort the array contents first

6. Shashank on June 10, 2015 at 1:49 pm said:

class CountPairs
{
public static void main (String[] args)
{
Integer a[] = new Integer[] {7,6,23,19,10,11,9,3,15};
int count = 0;
int k = 4;
Map map= new HashMap();
for (int i=0;i<a.length;i++) {
if (!map.containsKey(a[i]))
map.put(a[i],1);
}

for (int i=0;i<a.length;i++) {
if (map.containsKey(a[i]+k))
count++;
if (map.containsKey(a[i]-k))
count++;
map.remove(a[i]);
}
System.out.println("Pairs = "+count);
}
}

7. Time complexity seems like not O(nlogn). Can some one please explain this??

8. pawan singh on July 6, 2015 at 3:44 pm said:

#include
#include
#include
using namespace std;

int main()
{

int a[8]={7,623,19,10,11,9,3,15};
int k=4,temp,n=8;
int q=0,m,o=0,w=0;
cout<<"Array is :";
for(int y=0;y<8;y++)
{
cout<<a[y]<<" ";
}
cout<<"\n\nDifference b/w pairs is:"<<k<<"\n\nPairs Are :\n\n";
while(q<n)
{
while(o<n)
{
if((a[w]-a[q]) == k)
{
cout<<a[q]<<","<<a[w]<<"\n";
}
w++;
o++;
}
q++;
w=0;
o=0;
}
getch();
}

9. Dheeraj on July 9, 2015 at 3:01 am said:

@pawansingh It looks the complexity is not O(nlogn) correct me if I am wrong

10. Chaitanya on July 19, 2015 at 2:34 pm said:

Hey, I have one different approach let me know what you guys think of it.

(Python)Pseudo Code:
Example k=4 and a[]={7,6,23,19,10,11,9,3,15}
for i in a: #i = 7 at iter1, then 6, then 23 and so on
find = i + k # add “k” to each of them
binarySearch(a, find) # search for “find” in array a[]

11. Implementation using HashSet

public class SumTwoNums {

public static void main(String []args){
int diff=0;
int arr[]={2,6,4,8,9,14,16,-2,-6,0};

//Number to be checked
int num=8;

//HashSet to store array elements
HashSet hSet= new HashSet();

for(int i=0;i<arr.length;i++){
diff=num-arr[i];

if(hSet.contains(diff) && diff!=arr[i]){
System.out.println("Pair " + arr[i] + " + " + diff + " = " + num);
}
}
}
}

//Tested with Positive and Negative numbers

/*
*Output
*Pair 6 + 2 = 8
*Pair -6 + 14 = 8
*Pair 0 + 8 = 8
*/

12. sort the array O(nlgn)
Fix two indices (i & j) on the start. Move one if diff is less than required else the other. If the diff is equal to required diff print the values at i and j and move both i and j.