The GATE Grind

GATE 2020 CS – Question 58

Programming and Data Structures · Programming in C · 2 marks · Numerical answer

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}$.

More Programming in C questions

All Programming in C questions →