GATE 2026 CS1 Q.61: solution and answer

GATE 2026 · CS1Q.61 · 2 marks · NAT

Consider the recursive functions represented by the following code segment:

int bar(int n){
    if (n == 1) return 0;
    else return 1 + bar(n/2);
}

int foo(int n){
    if (n == 1) return 1;
    else return 1 + foo(bar(n));
}

The smallest positive integer n for which foo(n) returns 5 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 smallest positive integer $n$ for which foo(n) returns 5 is $65536$ .

Official answer: 65536Source: Official answer key, GATE 2026 CS1 (IIT Guwahati)

foo(n) unwinds as 1 + foo(bar(n)) until the argument becomes 1, where foo(1)=1. So foo(n)=5 means exactly 4 applications of bar are needed to bring n down to 1: n0=n → n1=bar(n0) → n2=bar(n1) → n3=bar(n2) → n4=bar(n3)=1, with n0, n1, n2, n3 all ≠ 1.
bar(m) repeatedly integer-halves m until it reaches 1, counting the halvings — tracing the recursion shows this is exactly bar(m) = ⌊log₂ m⌋ for every m ≥ 1 (verified on bar(2)=1, bar(3)=1, bar(4)=2, bar(7)=2, bar(8)=3).
bar(n3)=1 requires ⌊log₂ n3⌋ = 1, i.e. n3 ∈ {2,3}. Since ⌊log₂ ·⌋ is non-decreasing, the smallest n3 gives the smallest possible value to build back from at every later stage, so take the minimal n3 = 2.
bar(n2) = n3 = 2 requires ⌊log₂ n2⌋ = 2, i.e. n2 ∈ {4,5,6,7}; the minimal choice is n2 = 4.
bar(n1) = n2 = 4 requires ⌊log₂ n1⌋ = 4, i.e. n1 ∈ {16,...,31}; the minimal choice is n1 = 16.
bar(n0) = n1 = 16 requires ⌊log₂ n0⌋ = 16, i.e. n0 ∈ {65536,...,131071}; the minimal choice is n0 = 65536.
Verification by direct trace: bar(65536)=16, bar(16)=4, bar(4)=2, bar(2)=1, bar(1)=0, so foo(65536) = 1+foo(16) = 2+foo(4) = 3+foo(2) = 4+foo(1) = 4+1 = 5. Correct, and no smaller n achieves this since each stage above used the smallest possible value.

KEY IDEA

foo counts how many times bar must be applied to bring n down to 1, plus one; bar itself computes $⌊ lo g_{2} m ⌋$ (the number of integer-halvings needed to reach 1). Since $⌊ lo g_{2} m ⌋$ is non-decreasing in $m$ , the smallest $n$ reaching a target value after $k$ nested applications of bar is built from the inside out: at each stage pick the smallest number whose $⌊ lo g_{2} \cdot ⌋$ equals the previous stage's smallest value, i.e. exactly $2^{value}$ .

WATCH OUT FOR

Confusing bar(n) with n halved once (giving bar(n) = n/2) instead of recognizing it as the iterated-halving count $⌊ lo g_{2} n ⌋$ ; this leads to solving $n / 2^{4} = 1 \Rightarrow n = 16$ , missing that foo calls bar fresh on each level (nesting $⌊ lo g_{2} ⌋$ four times, not dividing by 2 four times).

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

GATE 2026 CS1 Q.61: solution and answer

Answer and solution

More Recursion questions