GATE 2017 CS (CS2) – Question 47
The following fragment divides x by y using repeated subtraction. All variables x,y,q,r are unsigned int. Which precondition ensures termination with x == y*q + r?
while (r >= y) {
r=r-y;
q=q+1;
}Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) (q == 0) && (r == x) && (y > 0)
Explanation
Initialize q=0,r=x so x=yq+r holds. Each iteration subtracts y from r and adds one to q, preserving this invariant. Positive y makes r strictly decrease without underflow because the guard checks r≥y. Termination then gives 0≤r<y and the required quotient identity. All conditions are present only in C.