in Programming edited by
22 votes

Consider the following PASCAL program segment:

if i mod 2 = 0 then
    while i >= 0 do 
        i := i div 2;
        if i mod 2 < > 0  then i := i - 1;
        else i := i – 2;

An appropriate loop-invariant for the while-loop is ________

in Programming edited by


out of syllabus ?
plz tell me  loop-invariant is in gate syllabus or not.....????
yes in syllabus .. syllabus is not defined as such .so you need to read this topic.
thank u sir

Subscribe to GO Classes for GATE CSE 2022

3 Answers

25 votes
Best answer

Loop invariant is some condition which holds at the end of each iteration of the loop. i.e. it is "invariant" => does not vary (or change). It might change inside one iteration, but it will be true at the end of every iteration.

We often use loop invariants to prove that our algorithm works correctly.

In the given program, a loop invariant is:

i mod 2 = 0

i.e. i is even after every iteration.

One can verify this as follows:

  • Before the execution of first iteration the loop invariant is true, because of this line of code: 
    if i mod 2 = 0 then
  • In every iteration, we divide i by $2$, so now i will be either odd or even. 
    • If odd, we subtract 1 from i 
      if i mod 2 < > 0  then i := i - 1; 
    • so it's now even.
    • otherwise, if even, we subtract 2 from i 
      else i := i – 2;
    • so, it remains even
  • So, at the end of every iteration i remains even.

selected by


this link is not working

meaning of symbol 

< >

is not equal to 

18 votes
A loop invariant is a condition that is always be same before the loop starts , while in the loop and after the loop ends for each iteration.

Here $i \mod2 = 0$ is the loop invariant.
edited by


is it applicable only for conditional statements?
loop invariant is a condition so it is applicable to conditional statements only ..yes we can say this ..
loop invariants are true even if the loop condition is false ...
Recently I studied that loop invariant may be or may not be true during iteration of the loop. Is this statement correct?

Yes, that will happen after last iteration.
11 votes

A loop invariant is a condition [among program variables] that is necessarily true immediately before and immediately after each iteration of a loop. (Note that this says nothing about its truth or falsity part way through an iteration.)


In simple words, a loop invariant is some predicate (condition) that holds for every iteration of the loop.

  • For example, let's look at a simple for loop that looks like this:
                int j = 9;
                for(int i=0; i<10; i++)  

In this example it is true (for every iteration) that i + j == 9. A weaker invariant that is also true is that i >= 0 && i < 10 (because this is the continuation condition!) or that j <= 9 && j >= 0.

  • The loop invariants will be true on entry into a loop and following each iteration, so that on exit from the loop both the loop invariants and the loop termination condition can be guaranteed.
Solution : An appropriate loop-invariant for the while-loop is i mod 2 = 0
                (i.e. ' i ' must be even, else the loop breaks when ' i ' is odd)
edited by


How can i mod2==0 be loop invariant...

For i=6, 6%2==0[ In while loop as i>=0 ]

Then i=3, 3%2!=0[ In while loop as i>=0 ]

Then i=i-1, making i=2

For i=2, i%2==0[ In while loop as i>=0 ]

Then i=i-2, making i=0

For i=0, i%2==0[ In while loop as i==0 ]

Then i=i-2, making i=-2[OUT OF LOOP]

SO loop invariant should be i>=0.

@bikram sir, how come i%2=0 is the loopinvaiant, as it may or my nt be equal to zero right??
instead shouldnt it be i>0 ??
Yes, in above example, i >=0 is loop invariant .. i value must be positive otherwise it is out of the loop ..

But in given Gate question i %2 ==0 is loop invariant ..
@Bikram Sir what can we say about loop invariant condition on termination of loop?? Can it be false then or it has to be true in order to prove correctness of the program at termination also?

No after termination it need not be true :

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

Loop invariant here is i+j= 9. at the end of termination i+j= 10.

edited by

okay so how do we relate loop invariants to looping conditions??

+ i think in the code 

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

After the loop terminates i=10 and j=-1 i+j=10+(-1)=9. 


Related questions

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