Consider the following program fragment for reversing the digits in a given…
2004
Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = D1D2…Dm
int n, rev;
rev = 0;
while (n > 0)
{
rev = rev*10 + n%10;
n = n/10;
}The loop invariant condition at the end of the ith iteration is:
- A.
n = D1D2….Dm-i and rev = DmDm-1…Dm-i+1
- B.
n = Dm-i+1…Dm-1Dm and rev = Dm-1….D2D1
- C.
n != rev
- D.
n = D1D2….Dm and rev = DmDm-1…D2D1
Attempted by 31 students.
Show answer & explanation
Correct answer: A
Loop invariant: After i iterations, n is the prefix consisting of the first m-i digits (D1 D2 … Dm-i) and rev is the reverse of the suffix of length i, i.e. rev = Dm Dm-1 … Dm-i+1.
Initialization (i = 0): Before the loop starts, rev = 0 (empty reversed suffix) and n = D1 D2 … Dm, which matches the invariant for i = 0.
Maintenance (i to i+1): Suppose after i iterations the invariant holds: n = D1…Dm-i and rev = Dm…Dm-i+1. In the next iteration the loop does d = n % 10 (which equals Dm-i), updates rev = rev*10 + d (so rev becomes Dm…Dm-i), and updates n = n / 10 (integer division) so n becomes D1…Dm-i-1. Thus the invariant holds for i+1.
Termination: When the loop ends, n = 0 and i = m, so rev contains Dm…D1, which is the full reversal of the original number.
Conclusion: The invariant correctly describes the relationship between n and rev after any number of iterations and explains why the algorithm produces the reversed integer when it terminates.