The following function computes XY 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?
The following function computes XY 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? Correct Answer X<sup>Y</sup> = res * a<sup>b</sup>
Consider X = 2, Y = 5,
Before iteration 1: res =1, a = 2, b = 5, X = 2, Y = 5
For these values all options are true.
After iteration 1 and before iteration 2:
if (b%2 == 0) {a = a*a; b = b/2;}
else { res = res*a; b = b-1; } // res = 2, b= 4
}
So, res = 2, a= 2, b= 4, X = 2, Y = 5
After iteration 2 and before iteration 3:
if (b%2 == 0) {a = a*a; b = b/2;} // a = 4, b =4/2 =2
else { res = res*a; b = b-1; }
}
Res = 2, a= 4, b= 2, X = 2, Y =5
After iteration 3 and before iteration 4:
if (b%2 == 0) {a = a*a; b = b/2;} // a = 16, b =2/2 = 1
else { res = res*a; b = b-1; }
}
res = 2, a= 16, b = 1, X = 2, Y = 5
After iteration 4 and before iteration 5 :
if (b%2 == 0) {a = a*a; b = b/2;}
else { res = res*a; b = b-1; } // res = 32, b = 0
}
After this, while condition becomes false
Before all these iterations, only option c will be true for these values, All other become false before iteration 2.
