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 ith 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




algorithm