808 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.
recategorized | 808 views
0
What is Pascal like pseudo code?

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
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
:) ...
0
What is Pascal like pseudo code?

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
+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...
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)
+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?
i=1;
j=n;
if((a[1]+a[2]>M) OR (A[n]+a[n-1]<M))
else
{
while(a[i]+a[j]!=M)
{
if(a[i]+[J]<M) i++;
else j--;
}
print i ,j
}


1
2