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.
Correct : 65536
To find the smallest positive integer n, we need to trace the behavior of the two recursive functions, bar(n) and foo(n).
1. Analyzing the bar(n) function
The function bar(n) repeatedly divides n by 2 (using integer division) and adds 1 each time until n reaches 1. Mathematically, this computes the floor of the base-2 logarithm of n:
bar(n) = $\lfloor \log_2(n) \rfloor$
Important property: To find the smallest integer n that produces a specific result k from bar(n), we use the power of 2 formula: n = 2k.
2. Analyzing the foo(n) function
The function foo(n) adds 1 to the recursive result of foo(bar(n)) until it hits the base case of foo(1) = 1.
We are asked to find the smallest n such that foo(n) = 5. Let''s work backwards step-by-step to find the inputs.
3. Working Backwards to find n
- For foo(n) to return 5, the recursive call must return 4: foo(bar(n)) = 4.
- For a call to return 4, its recursive call must return 3: foo(bar(x)) = 3.
- Tracing this all the way down to the base case gives us a chain:
foo(n5) = 5 → foo(n4) = 4 → foo(n3) = 3 → foo(n2) = 2 → foo(n1) = 1.
Because the base case in the code is foo(1) = 1, we know our lowest level argument is exactly n1 = 1.
Now, let''s reverse the chain upwards to find the smallest required argument at each step, using our property n = 2k:
- We know n1 = 1.
- We need bar(n2) = n1 = 1. The smallest integer is 21 = 2.
- We need bar(n3) = n2 = 2. The smallest integer is 22 = 4.
- We need bar(n4) = n3 = 4. The smallest integer is 24 = 16.
- We need bar(n5) = n4 = 16. The smallest integer is 216 = 65536.
Therefore, the smallest positive integer n that causes foo(n) to return 5 is 65536.
Correct Answer: 65536
Similar Questions
Total Unique Visitors