Program to Find a Pair with Given Difference

  • Write a program to find pairs of numbers whose difference is K.

Given an array of integers of size N. We have to find pairs of numbers whose difference is equal to K.
For Example :
Input Array : 1 2 4 6 7 9 13 15 17 20
K = 9
Output : [4, 13]

Method 1 : Checking the difference of every possible pair of elements.
Let inputArray be an integer array of size N and we want to find a pairs having difference of K.
  • In this method, we will check the difference of every pair of elements in array.
  • Outer loop will fix one element(let it be X) and inner for loop will check X's difference with every other element. If the difference is equal to K then print current pair.
Time Complexity : O(n2)
Method 2 : By Sorting Input Array
Let inputArray be an integer array of size N and we want to find a pairs having difference of K.
  • Sort inputArray.
  • Initialize two variables i and j to the index of first and second element of inputArray.
  • If inputArray[j] - inputArray[i] == K, then print inputArray[i] and inputArray[j].
  • If inputArray[j] - inputArray[i] < K, then we need to increase the difference between elements. Hence, increment j.
  • If inputArray[j] - inputArray[i] > K, then we need to reduce the difference between two elements. Hence, increment i.
Time Complexity : O(nLogn)

C program to find pairs of numbers whose difference is K

#include <stdio.h>

/* Swap array element at index left and right */
void swap(int *array, int left, int right) {
    int temp;
    /* Swapping using a temp variable */
    temp = array[left];
    array[left]=array[right];
    array[right]=temp; 
}
 
void quickSort(int *array, int left, int right) {
    int pivot; 
    if (right > left) {
      /* Partition the given array into 
      two segment by calling partion function */
        pivot = partition(array, left, right);
     
        /* Recursively sort left and right sub array*/
        quickSort(array, left, pivot-1);
        quickSort(array, pivot+1, right);
    }
}
 
int partition(int *array, int left, int right) {
    int temp = left;
    int pivot = array[left];
    
    while(left < right) {
        /* From left side, search for a number
      greater than pivot element */ 
        while(array[left] <= pivot) 
            left++;
        /* From right side, search for a number 
      less than pivot element */ 
        while(array[right] > pivot) 
            right--;
    
        /*Swap array[left] and array[right] */
        if(left < right) 
            swap(array, left, right);
    }
   /* Put pivot element in it's currect position '*/ 
   array[temp] = array[right];
   array[right] = pivot;
   /* Return partition index. All elements left of 
   right index is < pivot whereas elements right 
   side of right index are > pivot element */ 
   return right;
}

/* This function find's two elements of a sorted 
array whose difference is equal to diff */
void getDifferencePair(int *array, int size, int diff) {
    int i = 0, j = 1;
    /* sort input array */
    quickSort(array, 0, size-1);
 
    while(i < size && j < size) {
        if(i != j && (array[j] - array[i] == diff)) {
            printf("%d, %d\n", array[i], array[j]);
            return;
        } else if (array[j] - array[i] < diff) {
            j++;
        } else {
            i++;
        }
    }
 
    printf("No Pair Found");
    return;
}
 
int main() {
    int array[10] = {1, 2, 4, 6, 7, 9, 13, 15, 17, 20};
    getDifferencePair(array, 10, 9);
    return 0;
}
Output
4, 13
Posted by
Labels: ,