GATE CSE 2016 Set 2 | Question: 35

Question

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?

• A. $X^{Y} = a^{b}$
• B. $(res * a)^{Y} = (res * X)^{b}$
• C. $X^{Y} = res * a^{b}$
• D. $X^{Y} = (res * a)^{b}$

Comments

How to choose value of X & Y?

---

close look

termination while loop is b=0 and return res

option c   res∗a'b   (a'b=1)

return =res

---

Just take a note of using updated values of and b while satisfying the options.

Answer 1

Let us take x = X and Y = 27 then execution goes as follow -->

Now at few random steps you can cross verify. Answer is (C) Part.

Comments

Intuition behind this solution is any number could be broken in terms of power of 2. For example n= 27.

27 = (16+8+2). :)

---

why are u extending too much??

Read my comment below best answer..

Answer 2

May be this works .........

Answer 3

by taking exmple we can solve it. Here i took X=4 & Y=2