# with - write a program to find minimum elements in array which has sum equals to given value

## find pair of numbers whose difference is an input value 'k' in an unsorted array (2)

As mentioned in the title, I want to find the pairs of elements whose difference is K

``````example k=4 and a[]={7 ,6 23,19,10,11,9,3,15}
output should be :
7,11
7,3
6,10
19,23
15,19
15,11``````

I have read the previous posts in SO " find pair of numbers in array that add to given sum"

In order to find an efficient solution, how much time does it take? Is the time complexity `O(nlogn)` or `O(n)`? I tried to do this by a divide and conquer technique, but i'm not getting any clue of exit condition...

If an efficient solution includes sorting the input array and manipulating elements using two pointers, then I think I should take minimum of `O(nlogn)`...

Is there any math related technique which brings solution in `O(n)`. Any help is appreciated..

A simple solution in O(n*Log(n)) is to sort your array and then go through your array with this function:

``````void find_pairs(int n, int array[], int k)
{
int first = 0;
int second = 0;
while (second < n)
{
while (array[second] < array[first]+k)
second++;
if (array[second] == array[first]+k)
printf("%d, %d\n", array[first], array[second]);
first++;
}
}``````

This solution does not use extra space unlike the solution with a hashtable.

One thing may be done using indexing in O(n)

• Take a boolean array `arr` indexed by the input list.
• For each integer `i` is in the input list then set `arr[i] = true`
• Traverse the entire `arr` from the lowest integer to the highest integer as follows:
• whenever you find a `true` at `i`th index, note down this index.
• see if there `arr[i+k]` is true. If yes then `i` and `i+k` numbers are the required pair
• else continue with the next integer `i+1` 