edited by
9,678 views
37 votes
37 votes

Let $a$ be an array containing $n$ integers in increasing order. The following algorithm determines whether there are two distinct numbers in the array whose difference is a specified number $S > 0$.

i = 0; j = 1;
while (j < n ){
         if (E) j++;
         else if (a[j] - a[i] == S) break;
         else i++;
}
if (j < n) printf("yes") else printf ("no");

Choose the correct expression for E.

  1. $a[j] - a[i] > S$
  2. $a[j] - a[i] < S$
  3. $a[i] - a[j] < S$
  4. $a[i] - a[j] > S$
edited by

4 Answers

Best answer
55 votes
55 votes

Answer is (B)

For some '$i$' if we find that difference of $(A[j] - A[i] <S)$ we increment '$j$' to make this difference wider so that it becomes equal to $S$ .

If at times difference becomes greater than $S$ we know that it wont reduce further for same '$i$' and so we increment the '$i$'.

We do it for each '$i$' if not found in previous iteration. until $i=n$

edited by
5 votes
5 votes

Since, it is mention in question that array is in increasing order.

a[ j ] - a[ i ] > S , if is true. Does it make any sense to increment j because, it will increase the gap between them by every increment.

Option A : Wrong

a[ j ] - a[ i ] < S , if is true. Now if we increment it will lead to increase in value of (a[ j ] - a[ i ]  say equal to x) which is required because x<S after every in it will come close to S and might equal to S, if there are exactly two distinct integer present who difference is S. 

Option B : Correct

a[ i ] - a[ j ] < S ,if is true. LHS has a negative value  and RHS  has a positive value. 

Option C : Wrong

a[ i ] - a[ j ] > S ,if is true , not all possible pair can formed. Ex:-

Iteration              index             index             expression                       output

 1                            0                   1               a[0] - a[1] >S                        i++

 2                            1                   1               a[1] - a[1] >S                        i++

 3                            2                   1               a[2] - a[1] >S                        doesn't matter

 

since pair (a[2] - a[0] ) is not considered what if this gives the unique S.

Option D : Wrong

4 votes
4 votes

Method – 1 :

i = 0; j = 1;
while (j < n ){
         if (E) j++;       // A     
         else if (a[j] - a[i] == S) break;  // B
         else i++;         // C
}
if (j < n) printf("yes") else printf ("no");   // D 

B :   else if (a[j] - a[i] == S) break;

we found the element and we have to break

D :  if (j < n) printf("yes") else printf ("no");

we are here means either we break out of the loop (in that case j<n or we found the element) OR we haven’t break out of the loop (we haven’t found our element and in that case j=n)  

Since (a[j] - a[i] == S) we already checked on B then we are left with two choices for E or A(assumed earlier) .

A : if (a[j] - a[i] >  S)  j++;

It means the difference is already greater than S and by doing j++ we are going to make even more greater. In that case our difference will never reaches the S. So clearly this is not possible for A. It is possible case for C and indeed we are making the difference shorter by increasing i using i++ in else case.  

 

OR

 

A : if (a[j] - a[i]  <  S)  j++;

It means the difference is smaller than S and by doing j++ we are making it greater. In that case reaching nearer the S by making our difference wider. This is the correct choice for A.

Option B is the answer.


Method – 2

Option – A 

a[j] – a[i] > S

you run the while loop and first time if condition comes out to be true then condition always true till the end of the loop because incrementing j++ always makes difference would be even more wider .Each time first if condition only satisfies else if and else condition never have a chance. (due to given restriction that arrays is in increasing order.)

So, incorrect.

Option – C , D

a[i] – a[j] < S

if array is increasing than the a[i] – a[j] value always negative and since given S is positive than else if condition will never satisfy,

So, option B clearly.


Note : We can also transform the above code in reverse way checking and that also gives the correct result.

Link : Code

edited by
Answer:

Related questions

23 votes
23 votes
4 answers
2