GATE 2020 CS Q.48: solution and answer

GATE 2020 · CSQ.48 · 2 marks · NAT

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 ________.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The value returned by pp(3,4) is 81.

Official answer: 81Source: Official answer key, GATE 2020 CS (IIT Delhi)

tob(b,arr) writes the binary digits of b into arr[0..], LSB first: arr[i]=b%2 then b=b/2 each iteration, and returns the final value of the loop counter i (the bit count), since the for-loop tests b>0 after each increment.
Trace tob(4,arr): i=0,b=4: 4%2=0 -> arr[0]=0, b=2. i=1,b=2: 2%2=0 -> arr[1]=0, b=1. i=2,b=1: 1%2=1 -> arr[2]=1, b=0. i becomes 3; condition b>0 is false, loop exits. Returns i=3, so len=3 and arr=[0,0,1].
pp(3,4): ex=a=3, tot=1, len=3 (from the trace above).
Loop i=0: arr[0]=0, so tot is unchanged (tot=1); then ex=ex*ex=3*3=9.
Loop i=1: arr[1]=0, so tot is unchanged (tot=1); then ex=ex*ex=9*9=81.
Loop i=2: arr[2]=1, so tot=tot*ex=1*81=81; then ex=ex*ex=81*81=6561 (computed but never read again).
Loop ends since i=3=len. Function returns tot=81.
This is exponentiation-by-squaring: pp(a,b) computes $a^{b}$ using the binary representation of b (here $b = 4 = 10 0_{2}$ ), and indeed $3^{4} = 81$ .

KEY IDEA

tob(b,arr) writes the binary representation of b into arr[], least-significant bit first, and returns the bit count. pp(a,b) then uses those bits to compute $a^{b}$ by repeated squaring: ex holds $a^{2^{i}}$ at loop iteration i, and it is multiplied into tot exactly when bit i of b is 1 — this is the standard fast-exponentiation-by-squaring algorithm, so pp(a,b) returns $a^{b}$ .

WATCH OUT FOR

Forgetting that tob stores bits LSB-first (not MSB-first) and pairing the wrong bit with the wrong power of ex; or applying the final unused ex = ex*ex update after the loop has already produced tot, mistakenly squaring it again. Also common: stopping the trace of tob(4,arr) at i=2 instead of correctly returning i=3 (the increment happens before the loop condition is re-tested to false).

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 11 Pointers & arrays questions, with notes

GATE 2020 CS Q.48: solution and answer

Answer and solution

More Pointers & arrays questions