recategorized by
4,888 views
29 votes
29 votes
An array $A$ contains $n$ integers in non-decreasing order, $A[1] \leq A[2] \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $i, j,$ such that $A[i]+A[j]=a$ given integer $M$, if such $i, j$ exist.
recategorized by

6 Answers

Best answer
46 votes
46 votes
i = 1;
j = n;
while(i != j) {
   if(A[i] + A[j] == M) break;
   else if(A[i] + A[j] < M) i++;
   else j--;
}
edited by
6 votes
6 votes
i=1;
j=n;
if((a[1]+a[2]>M) OR (A[n]+a[n-1]<M))
  print Element not found
else
   {
    while(a[i]+a[j]!=M)
        { 
        if(a[i]+[J]<M) i++;
        else j--;
        }
   print i ,j
   }
   
4 votes
4 votes
This algorithm can be written easily with help of hash data structure. (Here they have not said whetehr we can use other DS or not , So I will use it )

1. First use hash table, to has first half no of this array. You can do it using O(1) time.

2. Then check for a-A[k], where n/2<=k<=n, by lookup using Hash table. You can do this is O(1) each lookup( Ideal Time compexity).

TIme compexity => O(N)
3 votes
3 votes

our works become simpler when we read the word its in increasing order...keep on adding the 2 consecutive  numbers

case 1:the sum is less than given element then continue

case 2:the sum is greater than given element then terminate and return -1

case 3:the sum is equal to given element then terminate and return the position of i and j

edited by

Related questions

35 votes
35 votes
4 answers
4
Kathleen asked Oct 4, 2014
22,917 views
Linked lists are not suitable data structures for which one of the following problems?Insertion sortBinary searchRadix sortPolynomial manipulation