12,001 views
32 votes
32 votes

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer.

Let $n = d_1\, d_2\, \ldots\, d_m$.

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 $i^{th}$ iteration is:

  1. $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}$

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

  3. $n \neq \text{rev}$

  4. $n=d_1\, d_2 \,\ldots\, d_m \qquad \mathbf{or} \qquad \text{rev} =d_m \,\ldots\, d_2\, d_1$

5 Answers

Best answer
37 votes
37 votes

A loop invariant is something that hold at the start of a loop, across each iteration (inside an iteration it can change but before the iteration ends original condition must be true) and at the end also. So, we can check for the satisfiability of the condition at the loop header for start of the loop, for each iteration and also at the exit.

Here, in each iteration the right most digit of n, is moving to the right end of rev. So, answer is (A). i.e. the $2$ conditions given in $(A)$ choice are true on entry to loop, after each iteration (not necessarily during an iteration), and at end of loop.

edited by
28 votes
28 votes

Loop invariant is a condition which is true in every iteration.

So lets take an example say n = 123 where d1=1,d2=2,d3=3

  Iteration 1 :    rev = 3  n = 12    or rev = d3  and n = d1d2
  Iteration 2:    rev = 32  n = 1    or rev = d3d2  and n = d1
  Iteration 3:    rev = 321  n = 0    or rev=d3d2d1  and n=d0

So in general we are getting n = d1d2...dm-i and rev = dmdm-1.....dm-i+1 in every iteration. So option A is true.n=d1d2dmi and rev=dmdm1dmi+1

4 votes
4 votes

Loop invariant must hold at the end of the iteration. In the given code, the least significant digit is taken from n and added to rev. So, at the end of ith iteration, n will have its least significant bits removed and they will be seen in rev. So, answer is (A).

4 votes
4 votes

we can solve it by leting some values like n=123 and then check by option for ith iteration i.e. i=1 or i=2. Option A will satisfy.

Answer:

Related questions

26 votes
26 votes
5 answers
1
Kathleen asked Sep 18, 2014
6,900 views
Choose the best matching between the programming styles in Group 1 and their characteristics in Group 2.$$\begin{array}{|ll|ll|}\hline \rlap{\textbf{Group 1}} & & \rlap{...
24 votes
24 votes
3 answers
4
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...