1.4k views

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$

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
+2
arjun sir .. am not clear about loop invariant ... pls explain more ... i googled out but not getting clearly ....
+6

It is pretty simple. "Invariant" means should not be changing, Now, loop invariant is some predicate that holds on

1. first entry to loop
2. across each iteration
3. exit of loop

But it can change within a loop. For example we can do sum++ and sum-- inside an iterations and still sum = c can be a loop invariant.

0
thank you....:)
0

I can understand the definition but not why option A here.

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

In every iteration,rev ,n are changing so where s the loop invariant?Plz xplain

0
see now, the condition checking is "across" each iterations- not at any point inside every iteration.
+21

A loop invariant is some condition that holds for every iteration of the loop.

Three properties of the loop invariant-

1) Initialization- It is true prior to the 1st iteration of the loop.
2) Maintenance - If it is true before an iteration of the loop, it remains true before the next iteration.
and
The most important one-
3)Termination-  When the loop terminates, this property, along with termination conditions, helps to show that the algorithm is correct.

See Code below-

int j = 9;
for(int i=0; i<10; i++)
j--;

Here at any iteration "i+j ==9" this predicate (condition) always holds, So it is loop invariant.
After the loop terminates i=10 and j=-1 i+j=10+(-1)=9.

Now consider Insertion Sort. In this sorting, we have an array[1..n] we know at any iteration i ,Array elements from 1 to i-1 always sorted and at the end we get array elements from 1 to n in sorted order. So, loop invariant is A[1...i-1] sorted.

When we write any algorithm, our goal is to maintain loop invariants.

Consider Insertion sort again.
Step 1: initialize loop invariant: A[1] is sorted.
Step 2: Maintain loop invariant (A[1 to i-1] should be sorted for any i)
Step 3: After termination of the loop-

Once we get out of loop, we achieve our Goal (Sorting) If we maintain loop invariant.
loop terminates when i=n+1.
A[1...i-1]=A[1...n+1-1]=A[1...n]. So we get the sorted array at the end.

Here in this question, each time we are taking out Least significant digit of n, and appending it to rev.
Here for any i, what will be true for $n$ and $\text{rev}$ ?

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

–1
In B)

in place of 'or' if we have 'and' , then it also a possible answer
+1
I understand the concept but why option D is not the answer?
+1
Option D can be true at the beginning of first or end of last iteration but not true for any i. Say for i=3,  n is not $d_1d_2...d_m$ and rev is not $d_md_{m-1}...d_1$ .
+1
why option C can't be true even though the invariant is satisfying across every iteration..??
+1
take n = 33 only now condition c fails. i.e. reprated value
0
Please include this answer in GO book as well. Excellent explanation. Thank you Sachin.

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

0
I understand the concept but why option D is not the answer?
0
c should also be true
+1
@suvasish, $C$ option can not be true for all the values of  $n$.

for simple example lets take $n$=$99$;

then when $i$=$1$, rev=$9$ and $n$=$9$

you can see here rev=$n$, and loop variant is not satisfied.
Hello sir,

I have taken n=128,  after running code I got below output at each iteration:

Iteration 1(n=12, rev=8)

Iteration 2(n=1, rev=82)

Iteration 3(n=0, rev=821)

Now, as above output I can conclude that option c(n!=rev) should be right answer.

Please clarify if observed something wrong, thanks!
0
If we take n=1111 then after 2nd iteration, we would have n=11 and rev=11, which says n=rev, so this can't be the loop invariant.