GATE CS 2016 Set 1 Q.44 (CS Q.34): Pointers, Arrays and Strings

The following function computes the maximum value contained in an integer array p[] of size $n$ ( $n \ge 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 != n

b != 0

b > (a + 1)

b != a

Official answer and solution

Official answer: D
From: Official GATE 2016 answer key

Solution

Analyze the loop invariant of the two-pointer maximum-finding algorithm.

The function uses two pointers a (starting at 0) and b (starting at $n - 1$ ).

In each iteration:

If p[a] <= p[b], p[a] cannot be the unique maximum in the remaining range $[a, b]$ because p[b] is at least as large. The pointer a is incremented (a = a + 1).
Otherwise (p[a] > p[b]), p[b] cannot be the maximum in the range $[a, b]$ . The pointer b is decremented (b = b - 1).

In every step, the search window $[a, b]$ shrinks by exactly 1 element while preserving the property that the true maximum lies within $[a, b]$ .

The search completes when only a single element remains, i.e., when $a == b$ . At that point, the loop must terminate so that return p[a]; returns the maximum element.

Therefore, the while loop should continue as long as $a \ne b$ , which is given by b != a.

Final answer

Common trap

Choosing a != n, which would run the pointers past each other and cause out-of-bounds indexing.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 44 of 65, printed as CS Q.34
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source