GATE 2015 CS – Question 65

Programming and Data Structures · Programming in C · 2 marks · Multiple choice

Consider the following pseudo code, where $x$ and $y$ are positive integers.

begin
    q := 0
    r := x
    while r >= y do
    begin
        r := r - y
        q := q + 1
    end
end

The post condition that needs to be satisfied after the program terminates is

$\{r = qx + y \wedge r < y\}$
$\{x = qy + r \wedge r < y\}$
$\{y = qx + r \wedge 0 < r < y\}$
$\{q + 1 < r - y \wedge y > 0\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\{x = qy + r \wedge r < y\}$

Explanation

The loop repeatedly subtracts $y$ from $r$, starting from $r = x$ and counting the subtractions in $q$. Each step keeps $x = qy + r$ true, and the loop stops when $r < y$. So after the program ends, $x = qy + r$ and $r < y$, which is integer division of $x$ by $y$.