Consider the following C program: main() { int x, y, m, n; scanf("%d %d", &x, &y); /* Assume x > 0 and y > 0 */ m = x; n = y; while (m != n) { if (m > n) m = m - n; else n = n - m; } printf("%d", m); } The program computes A. x + y using repeated subtraction B. x mod y using repeated subtraction C. the greatest common divisor of x and y D. the least common multiple of x and y

GATE 2004 · Algorithms · Identify Function · medium

Answer: The program computes and prints the greatest common divisor of x and y. Answer: C.

1. Identify the loop invariant: The fundamental property of GCD: GCD(a,b) = GCD(a-b,b). The loop preserves GCD(m,n) = GCD(x,y) at each step because we only replace the larger by the difference. This is the subtraction-based Euclidean algorithm.
2. Determine the termination condition: The loop terminates when m == n. At that point GCD(m,n) = GCD(m,m) = m. Since the loop invariant holds throughout, m = GCD(x,y). The program prints this value. Trace: x=12,y=8 -> m=4,n=8 -> m=4,n=4 -> print 4 = GCD(12,8). Correct.