GATE CS 2017 Set 2 Q.37 (CS Q.37): Data Types, Operators and Control Flow

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 terminates in a state satisfying the condition x == (y*q + r)?

(q == r) && (r == 0)

(x > 0) && (r == x) && (y > 0)

(q == 0) && (r == x) && (y > 0)

(q == 0) && (y > 0)

Official answer and solution

Official answer: C
From: Official GATE 2017 answer key

Solution

Analyze the loop invariant and termination conditions for the integer division by repeated subtraction algorithm.

The given algorithm computes quotient $q$ and remainder $r$ of $x$ divided by $y$ :

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

Loop Invariant: At every step of the loop, the relation $x = y \cdot q + r$ must be preserved.
Before entering the loop, if we set $q = 0$ and $r = x$ , we have: $y \cdot q + r = y \cdot 0 + x = x$ During each iteration, $r$ decreases by $y$ and $q$ increases by 1: $y(q + 1) + (r - y) = yq + y + r - y = yq + r = x$ Thus, $x = y \cdot q + r$ is an exact invariant.
Termination: The loop condition is r >= y. For the loop to terminate, $r$ must eventually drop below $y$ . If $y = 0$ , $r \ge 0$ is always true for unsigned int, causing an infinite loop. Therefore, we must have $y > 0$ .

Thus, the preconditions required are $q == 0$ , $r == x$ , and $y > 0$ , which corresponds to option C.

Final answer

Common trap

Overlooking that $q$ must be initialized to 0; if $q$ is not 0, $y \cdot q + r \ne x$ initially.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 2
Question: 37 of 65, printed as CS Q.37
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source