Consider the following program fragment for reversing the digits of a positive…

2004

Consider the following program fragment for reversing the digits of a positive integer to obtain a new integer. Let n = D1D2…Dm, where Dj denotes the j-th decimal digit from the left.

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:

Answer: A. n = D1D2…Dm−i and rev = DmDm−1…Dm−i+1 — CONCEPTA loop invariant is a relationship that is true at a chosen boundary of every loop iteration. It is established before the first iteration, preserved…

  1. A.

    n = D1D2…Dm−i and rev = DmDm−1…Dm−i+1

  2. B.

    n = Dm−i+1…Dm−1Dm and rev = Dm−1…D2D1

  3. C.

    n ≠ rev

  4. D.

    n = D1D2…Dm and rev = DmDm−1…D2D1

Attempted by 56 students.

Show answer & explanation

Correct answer: A

CONCEPT

A loop invariant is a relationship that is true at a chosen boundary of every loop iteration. It is established before the first iteration, preserved by one iteration, and then used at termination to explain the result.

For a digit-processing loop, the useful invariant must track which original digits remain unprocessed and which digits have already moved into the accumulator. Assume every intermediate value of rev*10 + n%10 and the final reversed value fit in C int, so signed overflow does not occur.

APPLICATION

  1. Initialization: Before any iteration, i = 0, n contains D1D2…Dm, and rev = 0 represents an empty processed suffix.

  2. For 0 ≤ i < m, assume that after i iterations, n contains the first m−i digits and rev contains the last i digits in reverse order. The current last digit of n is Dm−i.

  3. The expression n%10 extracts Dm−i. Multiplying rev by 10 opens one decimal place on its right, so rev = rev*10 + n%10 appends that digit to rev.

  4. Integer division n = n/10 removes the same last digit from n. Therefore n becomes D1D2…Dm−i−1, while rev becomes DmDm−1…Dm−i. This is the same relationship with i replaced by i+1.

  5. Termination: At i = m, n = 0; the prefix D1…D0 is interpreted as empty, and rev contains DmDm−1…D1, the complete reversed digit sequence. Because rev is an integer, any leading zero in that reversed sequence is not displayed.

CROSS-CHECK

Trace the input 12345. Each iteration removes the rightmost digit from n and appends it to rev:

Iteration i

n

rev

0

12345

0

1

1234

5

2

123

54

3

12

543

4

1

5432

5

0

54321

CONTRAST

  • A relation that keeps n as a suffix ending at Dm does not reflect removal of the rightmost digit by integer division.

  • The condition n ≠ rev gives no structural account of the digits and is false, for example, after one iteration on input 11.

  • A relation that keeps every original digit in both variables is independent of i and describes neither an intermediate state nor the variable updates.

RESULT

n = D1D2…Dm−i and rev = DmDm−1…Dm−i+1

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…