GATE CS 2004 Q32 — Programming in C

A loop invariant is a condition that holds true before and after each iteration of a loop.

Let the initial value of $n$ be represented as a sequence of $m$ digits: $n = d_1 d_2 \ldots d_m$.

Let us trace the values of $n$ and $\text{rev}$ at the end of the first few iterations:

• Before the loop starts ($i = 0$):
  • $n = d_1 d_2 \ldots d_m$
  • $\text{rev} = 0$
• At the end of the $1^{\text{st}}$ iteration ($i = 1$):
  • $\text{rev} = 0 \times 10 + (n \% 10) = d_m$
  • $n = n / 10 = d_1 d_2 \ldots d_{m-1}$
• At the end of the $2^{\text{nd}}$ iteration ($i = 2$):
  • $\text{rev} = d_m \times 10 + d_{m-1} = d_m d_{m-1}$
  • $n = d_1 d_2 \ldots d_{m-2}$

By induction, at the end of the $i^{\text{th}}$ iteration:

• The remaining number $n$ has its last $i$ digits removed: $$n = d_1 d_2 \ldots d_{m-i}$$
• The variable $\text{rev}$ contains the last $i$ digits of the original number in reverse order: $$\text{rev} = d_m d_{m-1} \ldots d_{m-i+1}$$

Both of these conditions must hold simultaneously (connected by an and operator).

Thus, the loop invariant at the end of the $i^{\text{th}}$ iteration is:

$$n = d_1 d_2 \ldots d_{m-i} \qquad \mathbf{and} \qquad \text{rev} = d_m d_{m-1} \ldots d_{m-i+1}$$

This matches Option A.