recategorized by
13,826 views
50 votes
50 votes

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?

  1. $X^{Y} = a^{b}$
  2. $(res * a)^{Y} = (res * X)^{b}$
  3. $X^{Y} = res * a^{b}$
  4. $X^{Y} = (res * a)^{b}$
recategorized by

7 Answers

Best answer
78 votes
78 votes

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

edited by
29 votes
29 votes
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.
7 votes
7 votes
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.
Answer:

Related questions

24 votes
24 votes
3 answers
3
Kathleen asked Sep 12, 2014
4,357 views
Consider the following PASCAL program segment:if i mod 2 = 0 then while i >= 0 do begin i := i div 2; if i mod 2 < 0 then i := i - 1; else i := i – 2; end;An appropria...
36 votes
36 votes
6 answers
4