GATE CS 2025 Set 2 Q23 — Programming in C

The given C code segment implements the subtraction-based Euclidean algorithm to compute the Greatest Common Divisor (GCD) of two positive integers $x$ and $y$.

Let's trace the execution of the do-while loop step-by-step with initial values $x = 126$ and $y = 105$:

1. Iteration 1:
   • Since $x > y$ ($126 > 105$), we update $x = x - y = 126 - 105 = 21$.
   • Now, $x = 21$ and $y = 105$.
   • Loop condition check: $x \neq y$ ($21 \neq 105$) is true. Loop continues.
2. Iteration 2:
   • Since $x > y$ ($21 > 105$) is false, we update $y = y - x = 105 - 21 = 84$.
   • Now, $x = 21$ and $y = 84$.
   • Loop condition check: $x \neq y$ ($21 \neq 84$) is true. Loop continues.
3. Iteration 3:
   • Since $x > y$ ($21 > 84$) is false, we update $y = y - x = 84 - 21 = 63$.
   • Now, $x = 21$ and $y = 63$.
   • Loop condition check: $x \neq y$ ($21 \neq 63$) is true. Loop continues.
4. Iteration 4:
   • Since $x > y$ ($21 > 63$) is false, we update $y = y - x = 63 - 21 = 42$.
   • Now, $x = 21$ and $y = 42$.
   • Loop condition check: $x \neq y$ ($21 \neq 42$) is true. Loop continues.
5. Iteration 5:
   • Since $x > y$ ($21 > 42$) is false, we update $y = y - x = 42 - 21 = 21$.
   • Now, $x = 21$ and $y = 21$.
   • Loop condition check: $x \neq y$ ($21 \neq 21$) is false. The loop terminates.

After the loop terminates, the printf statement prints the value of $x$, which is 21 (which is indeed $\text{GCD}(126, 105)$).