The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
685 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 (59.5k points)
recategorized by | 685 views

4 Answers

+23 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 Loyal (9k points)
edited by
0
final step is
else j--;

rt?
0
yes, my mistake
0
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.
0
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.
0
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.
0
If there are more than one such (i,j) pair will the program give correct result? Like suppose the given array is <1,1,2,3,4,4> and M=5 then there are 4 such (i,j) pairs. In the question it's just mentioned that there exists i,j .
0
Then this algorithm may not be linear time algorithm.

The algorithm they ask will stop when they found one such pair ( can be done in O(n) time).
0
Okay I got it @Prashant . Thank you
+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 Boss (14.2k points)
edited by
+1
But i and j need not be consecutive rt? if sum is > given element, we have to start with the next i rt?
0
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 Boss (42.6k points)
+1

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.

0
@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 (43 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

38,187 questions
45,688 answers
132,723 comments
49,654 users