in DS recategorized by
4,855 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.
in DS recategorized by
4.9k views

2 Comments

What is Pascal like pseudo code?
0
0
As an alternative to compilers generating machine code or assembly language, a more portable alternative is to generate a pseudo machine language that can then be transported to various machines and converted to their native code. This code is called Pascal like pseudo code.
1
1

6 Answers

46 votes
46 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--;
}
edited by

4 Comments

:) ...
1
1
What is Pascal like pseudo code?
0
0
Sir why can't it be in  linear time as we can store indexes i,j or can print them and continue with our loop  to find more such pairs in array ?
1
1
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 Comments

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.

1
1
@Akash :

n/2<=k<=n,

Why this condition?

I think it could be from 1 to n anywhere?
0
0

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

There is a typo. We can’t hash half of the elements of an array in O(1) time it will take O(n) time.

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).

Suppose there are 10 elements in an array and only by adding A[1] and A[2] we are getting a.

Your code will output there is no such pair exist.

Sir, I think both of your points are wrong. But the time complexity will be O(n). I tried to explain with code. 

 

1
1
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

2 Comments

But i and j need not be consecutive rt? if sum is > given element, we have to start with the next i rt?
1
1
yes you have got a point let me rethink...
0
0

Related questions