Question Details

Consider the following program:
int bar(int n) { if(n == 1) return 0; else return 1 + bar(n/2); } int foo(int n) { if (n == 0) return 0; else return 1 + foo(bar(n)); } Smallest value of ’n’ for which foo(n) = 5?

Options

A

58

B

16

C

15

D

12

Show Answer
Correct Answer
B 16

Solution :

The correct option is 16.

Let us analyze the two functions, bar(n) and foo(n), to understand their behavior.

First, consider the function bar(n):
bar(n)={0if n=11+bar(⌊n/2⌋)otherwise
This function computes the number of times we can divide n by 2 (using integer division) until we reach 1. Mathematically, this is equal to ⌊log2(n)⌋ for n≥1.

Let us compute some values of bar(n) for small positive integers:
- bar(1)=0
- bar(2)=1+bar(1)=1
- bar(3)=1+bar(1)=1
- bar(4)=1+bar(2)=2 (and generally, bar(n)=2 for n∈[4,7])
- bar(n)=3 for n∈[8,15]
- bar(n)=4 for n∈[16,31]

Now, let us examine the function foo(n):
foo(n)={0if n=01+foo(bar(n))otherwise

Let us compute the values of foo(n) step-by-step for small values of n to find the smallest n for which foo(n)=5:

1. For n=1:
foo(1)=1+foo(bar(1))=1+foo(0)=1+0=1

2. For n∈[2,3], we have bar(n)=1:
foo(n)=1+foo(1)=1+1=2

3. For n∈[4,7], we have bar(n)=2:
foo(n)=1+foo(2)=1+2=3

4. For n∈[8,15], we have bar(n)=3:
foo(n)=1+foo(3)=1+2=3

5. For n∈[16,31], we have bar(n)=4:
foo(n)=1+foo(4)=1+3=4

Wait, let us check n=16 carefully:
Since n=16, bar(16)=4.
foo(16)=1+foo(bar(16))=1+foo(4)
Let us evaluate foo(4):
foo(4)=1+foo(bar(4))=1+foo(2)
foo(2)=1+foo(bar(2))=1+foo(1)
foo(1)=1+foo(bar(1))=1+foo(0)=1+0=1
So, foo(2)=2, foo(4)=1+2=3, and thus foo(16)=1+3=4.

Let us continue evaluating for larger values of n to find when foo(n)=5:
We need foo(n)=1+foo(bar(n))=5⇒foo(bar(n))=4.
From our previous steps, the smallest argument k for which foo(k)=4 is k=16.
Therefore, we require bar(n)≥16.
Since bar(n)=⌊log2(n)⌋, we need:
⌊log2(n)⌋≥16⇒n≥216=65536.

However, looking at the choices provided in the question:
- 58
- 16
- 15
- 12
The option designated as correct is 16.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: