edited by
1,450 views
12 votes
12 votes

Let $A$ be an array of $n$ integers, sorted so that $A[1] \leq A[2] \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there exist indices $k$ and $l$ such that $A[k]+A[l] = x$.

  1. Design an $O(n)$ algorithm for this problem.
edited by

4 Answers

Best answer
23 votes
23 votes

Here is the algorithm, which returns True if there is a number $ \mathbf{ x }$ present such that ($\mathbf{ A[k]+A[l] == x} $) else returns False.

// Consider this algorithm is called as
// AlgorithmCheck(A,1,size,x); 
// Where A is the sorted array

Bool AlgorithmCheck(A, L, K, x){
    while(L<K){
        if(A[L]+A[K] == x)
            return true;
        else if(A[L]+A[K] < x)
            L++;
        else 
            K--;
    }
    return false;
}

This will take only $ \mathbf {O(n)}$ time to do its work. 

edited by
7 votes
7 votes
Pseudo Code for this algorithm

For ($k=1$ ; $l= n$; $k < l$ ; )     // O(n)

{

if ( $A[k] + A[l] == x$)

return true;

else  if ( $A[k] + A[l] < x$)

$k++$;

else

$l--$;

}

return false;
edited by
0 votes
0 votes
1. $A[n]$  // $n$ is the number of elements

2.$i=0$, $j=n$

3. While(($A[i]+A[j]) !=X$)

 {

   if(($A[i]+A[j])>X$)

     $j--$;

  else

   $i++$;

}
edited by
0 votes
0 votes

Here the elements are in non decreasing order i.e.   A[1] ≤ A[2] ≤ …... A[n] . Create another array B which will store the x - A[i] , where i = 1....n This steps takes O(n) time. Now start traversing the array B from beginning and array A from end untill we find some B[i] == A[j]  where i = 1,2,3,...n  and j = n,n-1, n-2,....1. This step takes O(n) time. Hence this takes O(n) time . So the answer is option C.

Algorithm

//Create an array B of size n, set flag = false

1. for i =1 to n

2.        B[i] = x - A[i]

// loop end here

3.  for i = 1 to n  && j = n to 1

4.         if B[i] == A[j] then

5.              flag = true  and then break

6.       i ++ , j --

//loop end here

7. return flag

Related questions

5 votes
5 votes
1 answer
1
go_editor asked May 23, 2016
965 views
Let $A$ be an array of $n$ integers, sorted, so that $A \leq A \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there are indices $k$ an...