Official PYQ · 2017Set 2 · Q37Programming in CMCQ1 mark

GATE CS 2017 Set 2 Q37 — Programming in C

Consider the C program fragment below which is meant to divide $x$ by $y$ using repeated subtractions. The variables $x$ , $y$ , $q$ and $r$ are all unsigned int.

while (r >= y) {
    r=r-y;
    q=q+1;
}

Which of the following conditions on the variables $x, y, q$ and $r$ before the execution of the fragment will ensure that the loop terminated in a state satisfying the condition $x==(y*q + r)$ ?

View worked solution

Answer: C

To ensure that the loop terminates in a state satisfying the relation $x == y \cdot q + r$ , we can use the concept of loop invariants.

Let us define the loop invariant as $I: x == y \cdot q + r$ .

Initialization: For the invariant to hold before the loop starts, we must initialize the variables such that $x == y \cdot q + r$ . If we set $q = 0$ and $r = x$ , the relation becomes: $y \cdot 0 + x = x$ which is always true.
Maintenance: During each iteration of the loop, let the new values of $q$ and $r$ be $q'$ and $r'$ respectively, where $q' = q + 1$ and $r' = r - y$ . Substituting these into the invariant expression: $y \cdot q' + r' = y(q + 1) + (r - y) = y \cdot q + y + r - y = y \cdot q + r$ Since the invariant holds before the iteration ( $y \cdot q + r == x$ ), it also holds after the iteration ( $y \cdot q' + r' == x$ ).
Termination: For the loop to terminate, the loop condition $r \ge y$ must eventually become false. Since $r$ is decremented by $y$ in each step, we must have $y > 0$ to ensure $r$ strictly decreases and the loop terminates. If $y = 0$ , the loop would run infinitely.

Combining these requirements, we need $(q == 0) \ \&\& \ (r == x) \ \&\& \ (y > 0)$ before the execution of the loop.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

More Programming in C questions

GATE CS 2017 Set 2 Q37 — Programming in C

Related questions