Program to Print all Pair of Numbers Whose Difference is K

  • Write a program to find a pair of number whose difference is equal to K
  • Algorithm to find a pair of array element whose difference is equal to given number.

Given an integer array of size N, we have to find pairs of numbers whose difference is equal to K. 

Input Array : [2 6 4 8 0 -4 10 7 -7 9]
K = 6
Output: 
[-4, 2]
[0, 6]
[2, 8]
[4, 10]

Let inputArray be an integer array of size N.
Using linear search : O(n2)
Algorithm to find a pair of number whose difference is K by using linear search
  • Using two loops, generate all possible pairs of numbers. Outer loop will fix an element and inner loop will check it's difference will other elements.
  • IF the difference of current pair of elements is equal to K, then print it else continue.
Time Complexity : O(n2)

C program to find a pair of number whose difference is K

#include <stdio.h>
#include <stdlib.h>

/* Prints pairs of numbers whose differnece is equal to K */
void printPairs(int *array, int size, int K){
    int i, j;
    
    for(i = 0; i < size; i++) {       
        for(j = i+1; j < size; j++) {
            if(abs(array[i] - array[j]) == K) {
               printf("[%d, %d]\n", array[i], array[j]);
            }
        }
    }
}

int main(){
    int array[10] = {2, 6, 4, 8, 0, -4, 10, 7, -7, 9}; 
    int i;
    
    printPairs(array, 10, 6);

    return 0;
}
Output
[2, 8]
[2, -4]
[6, 0]
[4, 10]
By sorting input array : O(NLogN)
  • Sort inputArray using any O(NLogN) average time sorting algorithm like quick sort or merge sort.
  • Initialize left and right index variables to 0.
  • Using a for loop, traverse inputArray using right index until right > N-1.
  • If abs(array[right]-array[left]) == K the print current pair and increment left and right index.
  • Else if difference between current pair is more than K (array[right] - array[left] > K), then we have to increment left index to reduce difference between pairs.
  • Else if difference current pair is less than K((array[right] - array[left] < K) then we have to increment right index to increase the difference between pairs.
Time Complexity : O(NLogN) 
#include <stdio.h>

/* Comparator function for qsort */
int compare(const void *a, const void *b) {
   return ( *(int*)a - *(int*)b );
}

/* Prints pairs of numbers whose differnece is equal to K */
void printPairs(int *array, int size, int K) {
 int left, right;
 /* Sort input array */
    qsort(array, size, sizeof(int), compare);
 
    for(left=right=0; right < size; ) {
        if(abs(array[right]-array[left]) == K) {
            printf("[%d, %d]\n", array[left], array[right]);
              left++;
              right++;
        } else if(array[right] - array[left] > K) {
            left++;
        } else {
            right++;
        }
    }   
}

int main(){
    int array[10] = {2, 6, 4, 8, 0, -4, 10, 7, -7, 9}; 
    int i;
    
    printPairs(array, 10, 6);

    return 0;
}
Output
[-4, 2]
[0, 6]
[2, 8]
[4, 10]
Posted by
Labels: ,