QUESTION 56 Consider the code segment given below: What function of x and n will this code...
Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
QUESTION 56
Consider the code segment given below:
int foo(int x, int n)
{
int val;
val = 1;
if (n>0)
{
if (n%2 == 1)
{
val = val * x;
val = val * foo(x*x, n/2);
}
}
return val;
}
What function of x and n will this code segment compute?
Show answer & explanation
This code implements fast exponentiation using binary exponentiation (exponentiation by squaring). When n is odd, it multiplies the current result by x and recursively computes foo(xx, n/2). When n is even, it skips the multiplication and recursively computes foo(xx, n/2). This pattern computes x^n in O(log n) time. The base case returns 1 when n≤0, which is correct since x^0 = 1.
Step-by-step Derivation:
Trace through examples:
foo(2, 5):
- n=5 is odd: val = 1 * 2 = 2, then val = 2 * foo(4, 2)
- foo(4, 2): n=2 is even: returns foo(16, 1)
- foo(16, 1): n=1 is odd: val = 1 * 16 = 16, then val = 16 * foo(256, 0)
- foo(256, 0): n=0, returns 1
- Backtrack: foo(16,1) = 161 = 16, foo(4,2) = 16, foo(2,5) = 216 = 32 = 2^5 ✓
foo(3, 4):
- n=4 is even: returns foo(9, 2)
- foo(9, 2): n=2 is even: returns foo(81, 1)
- foo(81, 1): n=1 is odd: val = 81, then val = 81 * foo(6561, 0)
- foo(6561, 0) = 1
- Backtrack: foo(81,1) = 81, foo(9,2) = 81, foo(3,4) = 81 = 3^4 ✓
The algorithm works by representing n in binary and using the property: x^n = (x^2)^(n/2) when n is even, and x^n = x * (x^2)^(n/2) when n is odd.