GATE CSE 2026 | Set 1 | Question: 51

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 $\mathrm{f} \circ \circ(\mathrm{n})$ returns $5$ is $\_\_\_\_$. (answer in integer)

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

Comments

if you observe the function closely , both $bar()$ and $foo()$ are just $log_2N$. 

Equation comes out to be $5 = 1+log_2(log_2(N))$ which would give us $N=2^{2^{4}}=2^{16}=65536$

credits to: @NullPointer_Pro

Answer 1

First of all understand what both of the functions are really doing.

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

Each call divides $n$ by $2$ and adds $1$ until it reaches $1.$
So, basically, it is finding $\lfloor \log_2n \rfloor.$

$\therefore \bbox[4pt, border: 1px solid black]{bar(n) = \lfloor \log_2n \rfloor}$          $-$ $(1)$

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

So, $foo(n) = 1 + foo(bar(n))$, using first equation we can write,

$\therefore \bbox[4pt, border: 1px solid black]{foo(n) = 1 + foo(\lfloor \log_2n \rfloor)}$          $-$ $(2)$

Base case : $foo(0) = 0$

Now, we need to find $n$ such that, $foo(n)=5$. So, we can open up $foo(n)$ in following way : 

Now, using base case we can say that, for $foo(log~log~log~log~log~n) = 0 $
$log~log~log~log~log~n = 0$

So, from this we can find $n$ as follows : 

​

$\mathbf{\therefore n = 2^{16} = 65536}$

Comments

@benzene06

Hi Benzene, you mistook the base case for foo(n) 

The answer should look as follows :

Can you please make the necessary edits to your answer? 

---

Nice bro, got clear understanding now...

Answer 2

bar(n) keeps dividing n by 2 until n becomes 1.

Examples:
bar(1) = 0
bar(2) = 1      (2 → 1)
bar(4) = 2      (4 → 2 → 1)
bar(16) = 4     (16 → 8 → 4 → 2 → 1)

foo(n) works as:
foo(n) = 1 + foo(bar(n))
and
foo(1) = 1

Now work backwards:

foo(1) = 1

To get foo(n) = 2:
bar(n) must be 1
Smallest n = 2

To get foo(n) = 3:
bar(n) must be 2
Smallest n = 4

To get foo(n) = 4:
bar(n) must be 4
Smallest n = 16

To get foo(n) = 5:
bar(n) must be 16
Smallest n whose bar(n) = 16 is 65536
(because 65536 = 2^16)

Verification:
foo(65536)
= 1 + foo(bar(65536))
= 1 + foo(16)
= 1 + (1 + foo(4))
= 1 + (1 + (1 + foo(2)))
= 1 + (1 + (1 + (1 + foo(1))))
= 1 + 1 + 1 + 1 + 1
= 5

Hence, the smallest positive integer n is:

65536