The Gateway to Computer Science Excellence
+7 votes

Consider the following program operating on four variables $u, v, x, y$, and two constants $X$ and $Y$.

x, y, u, v:= X, Y, Y, X;    
While (x ≠ y)  
    if (x > y) then x, v := x - y, v + u;
    else if (y > x) then y, u:= y - x, u + v;  
print ((x + y) / 2);  print ((u + v) / 2);  

Given $X > 0 \land Y > 0$, pick the true statement out of the following:

  1. The program prints $\text{gcd}(X, Y)$ and the first prime larger than both $X$ and $Y$.
  2. The program prints $\text{gcd}(X, Y)$ followed by $\text{lcm}(X, Y)$.
  3. The program prints $\text{gcd}(X, Y)$ followed by $\frac1 2 \times \text{lcm}(X, Y)$.
  4. The program prints $\frac1 2 \times \text{gcd}(X, Y)$ followed by $\frac1 2 \times \text{lcm}(X, Y)$.
  5. The program does none of the above.
in Algorithms by
edited by | 601 views
if we take X=5 ; Y =7

then A follows ; please check
Hi Guys,

First of all thanks to all of you for providing awesome solution.  One method is solving by small example. is there any other way to solve this problem ?

2 Answers

+9 votes
It prints with $gcd(x,y)$ and $lcm(x,y)$.

Consider $x,y,u,v=17,3,3,17$.

$X=14$, $v=20$

$X=11$, $v=23$

$X=8$, $v=26$

$X=5$, $v=29$

$X=2$, $v=32$

$Y=1$, $u=35$

$X=1$, $v=67$

This is the value obtained.

Lastly, printing $(x+y)/2$ and $(v+u)/2$ gives $1$ and $51$.
edited by
what about option c..????
+5 votes

Greatest Common Divisor of two number can be calculated using Euclid's Algorithm[1]

$$\begin{align}gcd(X,0) &= X \\ gcd(X,Y) &= gcd(Y,X \%Y)\end{align}$$

For $X,Y > 0$ this algorithm can be simplified as follows

$$gcd(X,Y) = \left\{\begin{matrix} X & X=Y& \\gcd(X-Y,Y)&X>Y & \\ gcd(X,Y-X)&X<Y & \end{matrix}\right.$$

Out of observation we learn that the given program is performing the same operation on two variable $x$ and $y$ initialized to $X$ and $Y$ respectively. Loop terminated with $x=y$, therefore $(x+y)/2$ i.e., average of two will return $x$ (or $y$), which is essentially $gcd(X,Y)$.

Next, let us propose a loop invariant[2] for this program[3]

$$2 X Y = (x \times v) + (y \times u)$$

The correctness of this program depends on this invariant, which must be true prior to the first iteration of the loop, during the execution of loop and with the termination of the loop it must express some useful property that program exhibits. Let's briefly show these three things.

  1. Initialization: The fact that this loop invariant holds prior to the first iteration of the loop can be seen by plugging in initial values of $x,y,u$ and $v$.
  2. Maintenance: Let us assume this loop invariant holds before $i^{th}$ iteration and we need to show that it holds after $i^{th}$ iteration as well. During $i^{th}$ iteration for $x>y$, $x = (x-y)$ and $u = (u+v)$. Substitue these new values in loop invariant we get $$\begin{align}2XY & = (x-y) \times v + y(u+v) \\ & = (x \times v) + (y \times u)\end{align}$$ And same will also be true for $x<y$.
  3. Termination: Loop terminates with $x=y$ and as shown earlier that $x=y=gcd(X,Y)$. Therefore, $$\begin{align}2XY & = (x \times v) + (x \times u) = x(u+v) \\ 2XY & = gcd(X,Y)(u+v) \end{align} $$ 

Rearranging above equation gives us[4]

$$\frac{XY}{gcd(X,Y)} = LCM(X,Y) = \frac{u+v}{2}$$



  1. GCD using Euclid's Algorithm
  2. Introduction to Algorithms, CLRS, 3rd edition, 2.1, Pg.18
  3. Edsger Dijkstra lecture at University of Newcastle 1992
  4. Reduction by the greatest common divisor

P.S In competitive examinations like GATE/TIFR the better strategy for such unfamiliar program is to try executing the program on different values, observe the result and compare with given options. However, in my opinion, understanding the underlining crux of such problems (when we are outside examination hall) is more important than just getting answers.


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,426 answers
95,226 users