GATE 2026 CS (CS1) – Question 61
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)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 65536
Explanation
Analyze function `bar(n)`:
- `bar(1) = 0`
- For $n > 1$, `bar(n) = 1 + bar(n/2)`. By induction, `bar(n) = \lfloor \log_2 n \rfloor` for any integer $n \ge 1$.
Analyze function `foo(n)`:
- `foo(1) = 1`
- For $n > 1$, `foo(n) = 1 + foo(bar(n))`.
For `foo(n)` to return 5:
- `foo(n) = 1 + foo(bar(n)) = 5 \implies foo(bar(n)) = 4`
- `foo(bar(n)) = 1 + foo(bar(bar(n))) = 4 \implies foo(bar(bar(n))) = 3`
- `foo(bar(bar(bar(n)))) = 2`
- `foo(bar(bar(bar(bar(n))))) = 1`
Since `foo(k) = 1` occurs when $k = 1$, we require:
$$\text{bar}(\text{bar}(\text{bar}(\text{bar}(n)))) = 1$$
To find the SMALLEST positive integer $n$, we work backwards finding the smallest integer at each step:
1. Smallest $k_1$ such that $\text{bar}(k_1) = 1$:
$\lfloor \log_2 k_1 \rfloor = 1 \implies$ smallest $k_1 = 2^1 = 2$.
2. Smallest $k_2$ such that $\text{bar}(k_2) = 2$:
$\lfloor \log_2 k_2 \rfloor = 2 \implies$ smallest $k_2 = 2^2 = 4$.
3. Smallest $k_3$ such that $\text{bar}(k_3) = 4$:
$\lfloor \log_2 k_3 \rfloor = 4 \implies$ smallest $k_3 = 2^4 = 16$.
4. Smallest $n$ such that $\text{bar}(n) = 16$:
$\lfloor \log_2 n \rfloor = 16 \implies$ smallest $n = 2^{16} = 65536$.
Therefore, the smallest positive integer $n$ is 65536.