GATE CSE 2016 | Set 1 | Question: 34

Question

 The following function computes the maximum value contained in an integer array $P[ \ ]$ of size $n$ $(n>=1)$.                  

int max (int *p,int n) {
    int a = 0, b=n-1;
    
    while (__________) {
        if (p[a]<= p[b]) {a = a+1;}
        else             {b = b-1;}
    }
    return p[a];
}

The missing loop condition is:

• A.  $a\ \ != n$ 
• B.  $b\ \ != 0$ 
• C.  $b>(a+1)$ 
• D.  $b\ \ != a$ 

Comments

If option C was b >= (a+1), then it would have worked!

---

@once_2019 why are thinking about factorial in this question 1st and 2nd option gave only for distraction

---

https://youtu.be/kkWGpD9OEuI?si=uQiMRYxi4sz8DGC-           video link

Answer 1

Answer is (D).

Hint : Given in the question itself that we start comparing the contents of an array  from $a[0]$ and $a [n-1]$ (converging from both side) then condition must be till both meet at a point and that point will be $a=b$.
Hence loop condition should be $a!=b$.

Option C fails for $n=2, p = [1, 2].$

Comments

Yes it’s correct, in that case also loop terminates when b=a 🙂

---

Above loop give correct answer when loop condition is :-

• b >= (a+1)
• b > a

but it gives wrong result on :

• b > (a+1)
• b >= a

---

@Kiyoshi During the return an additional condition should be checked if loop condition is $a+1 \le b$.

if(p[a]> p[b]){return p[a]};
else return p[b];

If the condition is $a + 1 <= b,$ the loop can terminate when $a$ and $b$ are adjacent. In this case a and b may point to two different elements so, the final maximum value must be explicitly determined by comparing $p[a]$ and $p[b]$ after the loop.

Answer 2

So option d is correct.

Answer 3

METHOD-1	METHOD-2