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

Take $X = 10, Y = 3$

In that case,

$ \underline{\text{Before Iteration 1:}}$

$res = 1 , a = 10 , b = 3$

All options are satisfied here.

$ \underline{\text{ Iteration 1:}}$

• $while(b!=0) \\  \implies 3!=0  \hspace{0.8cm} \checkmark$
• $if(b\%2==0) \\  \implies 3\%2==0  \hspace{0.8cm} \times$ 
• $else$
  $\quad res = res*a \\  \quad \implies res= 1*10 =10 $

              $b =b-1 \\  \implies b= 3-1 =2 $

$ \underline{\text{Before Iteration 2:}}$

$res = 10 , a = 10 , b = 2$

option A : $X^Y = a^b  \\  \implies 10^3 = 10^2 \hspace{0.8cm} \times$

option B : $(res * a)^Y = (res * X)^b  \\  \implies (10*10)^3 = (10*10)^2 \hspace{0.8cm} \times$

option C : $X^Y = res * a^b  \\  \implies 10^3 = 10 * 10^2 \hspace{0.8cm} \checkmark$

option D : $X^Y = (res*a)^b  \\  \implies 10^3 = (10*10)^2 \hspace{0.8cm} \times$

Lets see one more iteration to verify option C.

$ \underline{\text{ Iteration 2:}}$

$res = 10 , a = 10 , b = 2$

• $while(b!=0) \\  \implies 2!=0  \hspace{0.8cm} \checkmark$
• $if(b\%2==0) \\  \implies 2\%2==0  \hspace{0.8cm} \checkmark$ 
  $a= a*a$
  $\quad = 10*10=100$
  $b= \dfrac{b}{2}$
  $\quad = \dfrac{2}{2}=1$

$ \underline{\text{Before Iteration 3:}}$

$res = 10 , a = 100 , b = 1$

Option C : $X^Y = res * a^b  \\  \implies 10^3 = 10 * 100^1 \\ = 10^3 \hspace{0.8cm} \checkmark$

Option C is answer

Comments

correct sir.

---

But How do you think x  = 10 and y = 3 bcoz for x = 5 and y = 4 only option 2 is incorrect ?

---

Yeah Exactly..

Answer 2

Quick way to solve this will be to check the options for the last iteration i.e. when b=0. When b=0, at the start of the loop $X^{Y}$ value should be computed correctly in res. Only options C satisfies this. Hence Options C.

Comments

Finally when b=0, while condition fails and we wont get into the code inside it. Will that also be considered as an iteration?

---

Should we assume assignment operator as equal to operator

---

@mahendrapatel
No 
“==” is equal-to operator, returns True when both sides having same value, otherwise False.

Answer 3

OPTION C.

Comments

why  ???

---

We can do it simply by taking some values.

Answer 4

Lets take smaller values to save time, x=2,y=3

Set up variables:- a=2,b=3,res=1

Lets do one iteration:-

As b is odd,so we will goto else part , res=1*2=2 , b=3-1=2

Now values are a=2,b=2,res=2,x=2,y=3

Only option c wil hold.

Comments

@rahul sharma 5 @ akash.dinkar12 Sir, can we just stop at one iteration and check for options or should we completely run the code till while() gets false then we come out and try with values we got after the complete execution.

 

X=2 Y = 3

and when we completely run the code at end we get -

res = 8

a = 4 

b = 0

---

@iarnav 

You take any values and run complete code after that you check the option.

It is good practice for other question also.