Official PYQ · 2016Set 2 · Q35Programming in CMCQ1 mark

GATE CS 2016 Set 2 Q35 — Programming in C

The following function computes $X^{Y}$ for positive integers $X$ and $Y$ .

int exp (int X, int Y) { 
     int res =1, a = X, b = Y;
   
     while (b != 0) { 
         if (b % 2 == 0) {a = a * a; b = b/2; } 
         else         {res = res * a; b = b - 1; } 
     } 
     return res; 
}

Which one of the following conditions is TRUE before every iteration of the loop?

View worked solution

Answer: C

A loop invariant is a condition that remains true before and after each iteration of a loop. Let us verify the condition $X^Y = res \times a^b$ :

Initialization: Before the first iteration, $res = 1$ , $a = X$ , and $b = Y$ . Substituting these values into the expression: $res \times a^b = 1 \times X^Y = X^Y$ The condition holds true initially.
Maintenance: Assume the condition $X^Y = res \times a^b$ $X^{Y} = r es \times a^{b}$ holds before an iteration. Let $res'$ $r e s^{'}$ , $a'$ $a^{'}$ , and $b'$ $b^{'}$ be the values after the iteration:
- Case 1 ( $b$ is even): $a' = a^2$ , $b' = b/2$ , and $res' = res$ . $res' \times (a')^{b'} = res \times (a^2)^{b/2} = res \times a^b = X^Y$
- Case 2 ( $b$ is odd): $res' = res \times a$ , $a' = a$ , and $b' = b - 1$ . $res' \times (a')^{b'} = (res \times a) \times a^{b-1} = res \times a^b = X^Y$
In both cases, the relation is preserved.
Termination: When the loop terminates, $b = 0$ . The invariant gives: $X^Y = res \times a^0 = res \times 1 = res$ This correctly yields the final computed value of $X^Y$ .

Thus, the correct loop invariant is $X^Y = res \times a^b$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

More Programming in C questions

GATE CS 2016 Set 2 Q35 — Programming in C

Related questions