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);

    }

    }

  3. Thanks for your post

  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++){
    hSet.add(arr[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. skartik on December 31, 2016 at 1:29 am said:

    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.

Leave a Reply to skartik Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation