GATE 2025 CS (CS2) – Question 33
int x=126,y=105;
do {
if(x>y) x=x-y;
else y=y-x;
} while(x!=y);
printf("%d",x);The output of the given C code segment is ________. (Answer in integer)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 21
Explanation
This is the subtractive Euclidean algorithm for the gcd.
| x | y | action |
|---|---|---|
| 126 | 105 | $x>y$: $x=21$ |
| 21 | 105 | $y>x$: $y=84$ |
| 21 | 84 | $y=63$ |
| 21 | 63 | $y=42$ |
| 21 | 42 | $y=21$ |
| 21 | 21 | $x=y$: stop |
It prints $x=\gcd(126,105)=\mathbf{21}$.