The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1.2k 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$

asked in Programming by Veteran (69k points) | 1.2k views

3 Answers

+16 votes
Best answer

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.

answered by Veteran (346k points)
edited by
arjun sir .. am not clear about loop invariant ... pls explain more ... i googled out but not getting clearly ....

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. 

thank you....:)

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

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

 

Some more about Loop Invariant:

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

In B)

in place of 'or' if we have 'and' , then it also a possible answer
I understand the concept but why option D is not the answer?
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$ .
why option C can't be true even though the invariant is satisfying across every iteration..??
take n = 33 only now condition c fails. i.e. reprated value
Please include this answer in GO book as well. Excellent explanation. Thank you Sachin.
+11 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

 

answered by Loyal (3k points)
I understand the concept but why option D is not the answer?
c should also be true
@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.
0 votes
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!
answered by (43 points)
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.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,646 questions
40,193 answers
114,179 comments
38,666 users