- 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(n**

^{2})**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.

^{2})

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

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