Home
> Applied Algorithms, Arrays, Iteration, Sorting > Given N numbers, find pairs with difference K
Given N numbers, find pairs with difference K
Problem Statement : You have been given N numbers and a value K. Find the number of pairs in this given list of numbers whose difference is exactly equal to K.
This is a very simple one. Trying a brute force over all the elements is not being efficient. So what we’ll do is that we’ll sort the input array and apply a fine-tuned brute force as follows.
Once the array is sorted, for every number at position j, you start checking numbers backward from j to 0 (let us say using variable i, where i<j) and skip to checking for j+1 if the difference of the jth and ith element exceeds K. If you find their difference to be exactly K, you increment your count.
A very simple implementation of sorting. 🙂
Categories: Applied Algorithms, Arrays, Iteration, Sorting
Applied Algorithms, Arrays, Iteration, Sorting
All About Algorithms 
Buddy, Try using the ARRAY from counting sort
it could reduce the time even more… I hope you got the point
#NoBruteForce
How can you? I didn’t tell you the range for the N numbers. They might be as long as 10^50. Try doing a counting sort there. 🙂
PS: The question actually specified a limit of 10^40. 🙂
Ohhh okay… Sorry my bad… Yea counting sort do have that problem of range 😛
Aman, read theory of algorithms! Very imp…
What you could also do is do a binary search. Go from 0 to n-1 and do a binary search for and element with value k-A[i]. You get O(nlogn) and since you already sorted with nlogn, there is no additional cost. 🙂
@shrey..at first i thought how can you be sooo dumb but after reading limits i actually screwed myself…actually i did the somewhat same question(mine was to find pairs such that sum= k) in o (n) time complexity on my blog using another array.but the solution won’t work for higher limits.thanks for the solution.
Always solve problems keeping the worst case in mind. Unless otherwise specified.
if your n<=100000 take a look of my code i done it whout sorting i written a simplest c code for this
#include
int main()
{
int a[100000]={0};
int b[100000];
int n,k,q,m,i,count;
count=0;
scanf(“%d %d”,&n,&k);
for(q=0; q<n; q++)
{
scanf("%d",&b[q]);
m=b[q];
a[m]=1;
}
for(i=0; i<n; i++)
{
m=b[i];
m=m+k;
if(a[m]==1)
{
count++;
a[m]=0;
}
}
printf("%d",count);
return 0;
}
i think run time of my code will be minimum
Did you read the comments? How many times do I have to say, make algorithms for all cases. 😛
its not an argue its just an idea that i wanna share…. i am not rishit jain
oh… sorry
ok my take
sort the array and start for elements from higher end so in start j=n.
Now you know what number to search for A[j] ie A[j]-k. do this search in binary fashion in the set a[0:n-1]. suppose we got the number at x position.
Now for A[n-1] the corresponding number can not be after x position as A[n-1] <= A[n]
So for j=n-1 search element A[j] – k in the set A[0:x] in binary fashion.
keep on like this and every successful pair search would give reduce your effective search set for next coming numbers.
one more optimization can be before starting search in for the second pair for A[j] see if
A[j]-k < A[0] then no solution would be found as for the pair of A[j] we want smaller number than A[0].
public class NumberofPairs {
public static void main(String args[])
{
int[] a = {4,2,7,6,9,11,13};
int key = 2;
int count = 0;
for(int i = 0; i < a.length; i++)
{
for(int j=i+1; j< a.length; j++)
{
if(Math.abs(a[i]-a[j]) == key)
count++;
}
}
System.out.println(count);
}
}
Sorting an array itself will take minimum o(nlogn) using one of the efficient sorting techniques and then again iterating over the sorted array would take o(n). tha above source code will give o(n2), still not efficient but can be reduced down to nlogn.
What if i give an array of all 1’s and difference k=0…. In that case this is a O(n^2) algo
Well, if you have those many answers, you will obviously have to go over the array those many times 🙂 But yes, to clarify, what I suggested is not the worst-case complexity