GATE 2026 CS2 Q.61: solution and answer

GATE 2026 · CS2Q.61 · 2 marks · NAT

Consider the following ANSI-C function.

int func(int start, int end){
        int length=end+1-start;
        if((length<1)||(start<0)||(end<0)){ return(0); }
        if(length%3==0){
                return(func(start+1, end));
        } else if(length%3==1){
                return(1+func(start, end-1));
        } else {
                return(func(start+2, end));
        }
}

The maximum possible value that can be returned from this function is ______. (answer in integer)

Note: Ignore syntax errors (if any) in the function.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The maximum possible value that can be returned from func is $1$ .

Official answer: 1Source: Official answer key, GATE 2026 CS2 (IIT Guwahati)

Let $L = end - start + 1$ be the value of length at a call. Track only how $L mod 3$ evolves and how many +1s the recursion adds.
Also note start never decreases (it is passed as start, start+1, or start+2) and end never increases (it is passed as end or end-1). So once start >= 0 and end >= 0 hold initially, the recursion cannot terminate for a reason other than length < 1, except possibly through the one end - 1 step described below.
Branch $L mod 3 = 0$ : calls func(start+1, end), giving new length $L - 1$ . Since $L \equiv 0$ , the new residue is $(L - 1) mod 3 = 2$ . This branch adds $0$ to the return value.
Branch $L mod 3 = 1$ : calls 1+func(start, end-1), giving new length $L - 1$ . Since $L \equiv 1$ , the new residue is $(L - 1) mod 3 = 0$ . This branch adds exactly $1$ to the return value.
Branch $L mod 3 = 2$ : calls func(start+2, end), giving new length $L - 2$ . Since $L \equiv 2$ , the new residue is $(L - 2) mod 3 = 0$ . This branch adds $0$ to the return value.
So the residue-transition map is $0 \to 2$ , $1 \to 0$ , $2 \to 0$ , and only the transition out of residue $1$ ever adds a point.
The crucial observation: residue $1$ never appears as the TARGET of any transition — the only targets produced are $2$ (from $0$ ) and $0$ (from $1$ or $2$ ). So residue $1$ can occur only at the very first call (if the initial length is $\equiv 1 (mod 3)$ ) and can never recur later in the recursion.
Hence at most one +1 can ever be earned in any run, and it is earned only when the initial length satisfies $L_{0} \equiv 1 (mod 3)$ ; every subsequent step (cycling through residues $0$ and $2$ ) contributes $0$ until length < 1 triggers the base case returning $0$ .
Trace check with $L_{0} = 1$ (e.g. start = end = 0): $1 mod 3 = 1$ , so it returns 1+func(start, end-1). The inner call now has length $0 + 1 - 0 = 0 < 1$ — wait, recompute: func(0,-1) has length $= (- 1) + 1 - 0 = 0$ , so length<1 (and end<0) is true and it returns $0$ . Total $= 1 + 0 = 1$ .
Trace check with $L_{0} = 4$ : residues go $4 mod 3 = 1$ (+1) → length $3$ , residue $0$ (+0) → length $2$ , residue $2$ (+0) → length $0$ , which hits length<1 and returns $0$ . Total $= 1$ .
Since no sequence of lengths can ever revisit residue $1$ , no run can earn a second +1. The maximum possible return value is therefore $1$ , achieved by any starting pair with $(end - start + 1) \equiv 1 (mod 3)$ .

KEY IDEA

Since start never decreases and end never increases, the recursion is driven entirely by length $mod 3$ : the transition map is $0 \to 2$ , $1 \to 0$ , $2 \to 0$ , and only the $1 \to 0$ step ever adds +1. Because residue $1$ is never a target of any transition, it can occur only once (at the very start, if at all), so at most one point can ever be earned in the whole recursion.

WATCH OUT FOR

Assuming the +1 can be earned repeatedly (e.g. once per "cycle" of 3 in the original length) without checking which residues are actually reachable after the first step; tracing only one example instead of proving that residue $1$ can never recur rules out any larger value.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 9 Recursion questions, with notes

GATE 2026 CS2 Q.61: solution and answer

Answer and solution

More Recursion questions