Skip to content
GATEiit

GATE CSE 2026 Session 1 Q61: Smallest n for which foo(n) = 5 with foo(bar(n))

Question

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.

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 65536 (official GATE 2026 final answer key)

Concept used: bar(n) =⌊log⁡2n⌋= \lfloor \log_2 n \rfloor, so foo counts iterated logarithms.

First step: Work backwards: foo(n) = 2 first at n = 2, so foo(n) = 3 first when bar(n) = 2, i.e. n = 4; continue the pattern.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 1 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Programming and Data Structures PYQs

PracticePractise Programming and Data Structures questions →Full paperAll GATE CSE 2026 Session 1 questions →