GATE CSE 1995 | Question: 2.3

Question

Assume that $X$ and $Y$ are non-zero positive integers. What does the following Pascal program segment do?

while X <> Y do
if  X > Y then
    X := X - Y
else
    Y := Y - X;
write(X);

• A. Computes the LCM of two numbers

• B. Divides the larger number by the smaller number

• C. Computes the GCD of two numbers

• D. None of the above

Comments

while X <> Y && (X!=0 || Y!=0) do // I don't know if '&&' works in pascal
if  X > Y then                    //Even if this considered as comment or not.
    X := X - Y
else
    Y := Y - X;
write(X);

---

if anyone is struggling with <> .

it is nothing but not equal to in Pascal, means if we write x<>y  it is true if x is not equal to y. you can equate with x!=y in C.

---

Similar question – https://gateoverflow.in/1038/gate-cse-2004-question-41

Answer 1

Answer: C

Let $X = 3$ and $Y = 7$.

• $1^{\text{st}}$ pass: $X = 3, Y = 4$
• $2^{\text{nd}}$ pass: $X = 3, Y = 1$
• $3^{\text{rd}}$ pass: $X = 2, Y = 1$
• $4^{\text{th}}$ pass: $X = 1, Y = 1$

write $(X)$, which writes $1$.

Ref: https://en.wikipedia.org/wiki/Euclidean_algorithm

Answer 2

Apply Option Elimination

take X=6,Y=4

if Ans will 12 then LCM , 2 then GCD, 1 then Divides the larger number by the smaller number

Now Trace the code

Iteration1 :-X=2,Y=4

            2:-X=2,Y=2

Print 2 ; which is GCD

take another pair X=12,Y=8 which gives 4 means ans is GCD .

Hence C is the Correct Ans

Answer 3

The algorithm is based on below facts.

If we subtract smaller number from larger (we reduce larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.