The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
1.8k 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 (59.6k points) | 1.8k views

4 Answers

+20 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 (359k points)
edited by
+2
arjun sir .. am not clear about loop invariant ... pls explain more ... i googled out but not getting clearly ....
+8

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

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

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

–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?
+2
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.
+13 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 Active (3k points)
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.
0
b,c,d are not true because

b) is incorrect as loop invariant condition doesn't satisfy the correctness of the program i.e taking out Least significant digit of given n and appending it on right on rev.

c) is incorrect as if my input is 121121..then after 3rd iteration n=121 rev=121 i.e n=rev so failing the given loop invariant condition.

d) is incorrect as it satisfies only at start and end of last iteration but not for any intermediate i. (you can check it by any random example)

so A is true (which is well explained in above answers)
+2 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.

answered by (177 points)
0

What if we check option A for 0th iteration?

for n = d1d2d3 but, for rev it is d3...d4, What am I missing here?

0
According to me,whenever i used hit & trial method i used to solve it atleast for 2 to 3 values so that i can easily cancel out the options. So, here i'll go for atleast 2 to 3 iterations. And how u can reverse a no. without going through the loop, thats why hit & trial going wrong there..so please do atleast for some iterations.
0

No, I meant to say that according to the definition of Loop Invariant, the condition must be true even before execution starts. But for 0th iteration, it seems to violate option A(i know I'm wrong). For iterations 1,2,3 option A is true but for 0th, it's not (rev should be equal to d4, but was equal to dm...dm-i+1 viz d3...d4).

Thanks for the reply, I found the answer to my own question, same digits can't occur in n as well as rev, which was evident from the code, I missed that point which led to my confusion.

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 (71 points)
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.
0
Wow kya bat h sir g


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

40,976 questions
47,609 answers
146,779 comments
62,342 users