Find two elements from an array whose sum equals a given element
  • timecomplexity
  • linearithmictime
  • array
  • searching
  •   
  • Posted: 4 years ago
  • Updated: 2 years ago
  • Edit
  • answers (2)
  • views (6135)

Suppose you are given an array of n integers. You are asked to determine whether there exists two elements whose sum is exactly equal to another given integer x . Can you describe a \( \theta(nlogn) \) time algorithm?


Posted Answers

void find_split(int a[], int arr_size,int number)
{
int i,j = 0, first;
int num1 = 0, num2 = 0;
while (j != arr_size)
{
for(i =0; i < arr_size ; i++)
{
first = a[j];

if ((first + a[i]) == number)
{
num1 = first;
num2 = a[i];
}
}
j++;
}
printf("Both the numbers are %d and %d",num1,num2);
}

The algorithm will be :


  • Sort the array.
  • Take the first element of the array and do binary search to find ( x - first element) in the array.
  • If ( x - first element) is found, return true.
  • Else, repeat the binary search for the rest of the elements in the array.
  • If all the searches result false, return false.

Running time for merge sort is \( \theta(nlogn) \).
Running time for each binary search is \( O(logn) \).
So, running time for binary search of \( (n-1) \) elements is \( O(nlogn) \).
Therefore, total running time is \( \theta(nlogn) + O(nlogn) = \theta(nlogn) \).

public static boolean search2Numbers (int[] array, int x){

/* Sort the array */
Arrays.sort (array);

/* Index of first element */
int i = 0;
/* Index of last element */
int j = array.length - 1;

while (i < j) {

/* Check if the sum of the elements at index i and j equals x */
if (array[i] + array[j] == x)
return true;

/* If the sum is greater than x, decrease the sum */
elseif (array[i] + array[j] > x)
j--;

/* If the sum is less than x, increase the sum */
else
i++;

}

/* If there is no such pair */
return false;
}

You need to Sign In to post your solution.