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)
Answer
21
Explanation
The loop is the subtraction form of Euclid’s algorithm. Replacing the larger number by the difference of the two never changes their greatest common divisor, and the values keep shrinking until they are equal, so both end up as \(\gcd(126, 105)\).
Trace of \((x, y)\): \((126, 105) \to (21, 105) \to (21, 84) \to (21, 63) \to (21, 42) \to (21, 21)\). Now x!=y is false, the do-while loop exits and 21 is printed.
Answer: 21