The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+8 votes
549 views
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.
asked in DS by Veteran (69k points)
recategorized by | 549 views

4 Answers

+22 votes
Best answer
i = 1;
j = n;
while(i != j) {
   if(A[i] + A[j] == M) break;
   else if(A[i] + A[j] < M) i++;
   else j--;
}

 

answered by Boss (9.3k points)
selected by
final step is
else j--;

rt?
yes, my mistake
Suppose the value of 'M' is the first element of an array. Then your program will exit from while loop without giving right answer.

Correct me if i am wrong.
If such an i and j does not exist for a given array, Instead of iterating till half the array elements, We can simply do a check at the beginning of code like,

$if\ A[n-1]+A[n] < M$

$then\ return\ FAILURE$

So that this will save time.
Mr. arjun, Kindly look this,

Sorry to say but I think this is right code because If (A[i]+A[j] <M) then i++; because of the sum of first and last no. is smaller than the given value so you need to increase the sum to reach the value "M" That why we need to increase the index i to i+1.
+2 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

answered by Veteran (14.3k points)
edited by
But i and j need not be consecutive rt? if sum is > given element, we have to start with the next i rt?
yes you have got a point let me rethink...
+2 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)
answered by Veteran (49.5k points)

can u explain ur logic once again ,its really hard for me to understand.

what is the meaning of this line:

First use hash table, to has first half no of this array.

@Akash :

n/2<=k<=n,

Why this condition?

I think it could be from 1 to n anywhere?
+1 vote
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
   }
   

 

answered by (51 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,713 questions
40,262 answers
114,373 comments
38,894 users