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. 🙂

Advertisements
  1. April 27, 2012 at 6:29 pm

    Buddy, Try using the ARRAY from counting sort
    it could reduce the time even more… I hope you got the point
    #NoBruteForce

    • April 27, 2012 at 6:32 pm

      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. 🙂

  2. April 27, 2012 at 6:35 pm

    Ohhh okay… Sorry my bad… Yea counting sort do have that problem of range 😛

  3. April 27, 2012 at 8:32 pm

    Aman, read theory of algorithms! Very imp…

  4. April 27, 2012 at 8:34 pm

    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. 🙂

  5. April 27, 2012 at 9:00 pm

    @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.

    • April 27, 2012 at 9:09 pm

      Always solve problems keeping the worst case in mind. Unless otherwise specified.

  6. May 9, 2012 at 9:45 pm

    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

    • May 9, 2012 at 9:51 pm

      Did you read the comments? How many times do I have to say, make algorithms for all cases. 😛

      • May 9, 2012 at 9:57 pm

        its not an argue its just an idea that i wanna share…. i am not rishit jain

  7. May 9, 2012 at 10:05 pm

    oh… sorry

  8. anuj
    August 26, 2012 at 7:16 pm

    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].

  9. October 14, 2012 at 11:47 am

    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.

  10. Nitin
    August 27, 2013 at 1:09 am

    What if i give an array of all 1’s and difference k=0…. In that case this is a O(n^2) algo

    • December 5, 2014 at 10:57 am

      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

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: