GATE 2020 CS – Question 58
Consider the following C functions.
int tob(int b, int* arr) {
int i;
for(i=0; b>0; i++) {
if(b%2) arr[i]=1;
else arr[i]=0;
b = b/2;
}
return(i);
}
int pp(int a, int b) {
int arr[20];
int i, tot = 1, ex, len;
ex = a;
len = tob(b,arr);
for(i=0; i<len; i++) {
if(arr[i]==1)
tot = tot * ex;
ex = ex * ex;
}
return(tot);
}The value returned by pp(3,4) is ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 81 to 81
Explanation
`pp(a,b)` raises `a` to the power `b` by repeated squaring.
`tob(4, arr)` stores the binary digits of 4, least significant first: $4=100_2\Rightarrow arr=[0,0,1]$, `len = 3`.
Loop with `a=3`: `tot=1`, `ex=3`.
- $i=0$: `arr[0]=0`, `tot` stays 1; `ex = 3*3 = 9`.
- $i=1$: `arr[1]=0`, `tot` stays 1; `ex = 9*9 = 81`.
- $i=2$: `arr[2]=1`, `tot = 1*81 = 81`; `ex = 81*81`.
`pp(3,4)` returns $3^4=\mathbf{81}$.