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

- whenever you find a