GATE CSE 2004 | Question: 32

Question

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:

• A. $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}$

• B. $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$

• C. $n \neq \text{rev}$

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

Comments

https://www.geeksforgeeks.org/loop-invariant-condition-examples-sorting-algorithms/

---

3rd option's condition also gets violated whenever n is a palindrome number like N= 1221

---

lets try to understand all ooption with an example:

option a: n=d1d2....d(m-i)  AND rev=dm dm-1...d(m-i+1)
after i-th iteration 
n has lost its i digits ( shrink from right)
rev has collected those i digit in reverse order
which matches to given expression and thats what loop is doing..

option b: n= d(m-i+1)...d(m-1)dm  OR rev=d(m-i)...d2d1
its wrong because its assume n keeps the suffix and rev keeps the prefix reversed, but the program does the exact opposite

option c:  n is not equal rev 
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.

option d: n=d1d2..dm  OR  rev=dm..d2d1
as n is full original no. rev is always the complete reverse of that no.  
this is wrong because as it satisfies only at start and end of last iteration but during the loop, n is shrinking and rev is growing..


correct answer is A :
 

Answer 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.

Comments

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

Also, check loop invariant for Dijkstra’s algorithm. It will give in-depth understanding of the algorithm,

---

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.

---

@Arjun sir, what if n=10000 than how the invariant condition holds?

---

@Arjun sir is loop invariant in syllabus for 2021??

---

Another example of loop invariant following @Sachin Mittal 1 Sir’s comment on loop invariant for Dijkstra’s algorithm:-

The key idea, that Dijkstra will maintain as an invariant, is that $∀t ∈ V$, the algorithm computes an estimate $d[t]$ of the distance of $t$ from the source such that:

1. At any point in time, $d[t] ≥ d(s, t)$, and

2. when $t$ is finished, $d[t] = d(s, t)$.

 

---

@Sachin Mittal 1 Sir,
If possible, please make a video on concepts of Loop Invariants with some standard ques.

Answer 2

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=d1d2…dm−i and rev=dmdm−1…dm−i+1

Comments

@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.

---

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)

---

Nice explanation @meghna

Answer 3

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.

Comments

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 d₄, but was equal to d_m...d_m-i+1 viz d₃...d₄₎.

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.

---

I am stuck on the same. Did you get it resolved?

---

Quoted from question :

The loop invariant condition at the end of the $i^{th}$ iteration is:

 Not necessarily at the beginning.

Answer 4

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).

Comments

Can you please correct the thread title?

Answer 5

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!

Comments

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.

---

Wow kya bat h sir g

---

Option C fails for every even length palindrome number.

Answer 6

The loop invariant here means a condition that remains true after every iteration of the loop. In this program, after each iteration, the last digit of n is removed and added to rev. So, n always stores the remaining left (unprocessed) digits, while rev stores the right-side digits that have already been processed in reverse order. For example, if n = 1234, after the first iteration n = 123 and rev = 4, after the second iteration n = 12 and rev = 43. This pattern remains true in every iteration, which is why option A is the correct loop invariant.