GATE 2021 CS (CS2) – Question 33
Find SomeFunction(15,255).
int SomeFunction(int x,int y) {
if ((x==1)||(y==1)) return 1;
if (x==y) return x;
if (x>y) return SomeFunction(x-y,y);
if (y>x) return SomeFunction(x,y-x);
}Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 15 to 15
Explanation
This is the subtractive Euclidean algorithm: subtracting the smaller positive value from the larger preserves their gcd. Since 255=17×15, repeated subtraction reaches (15,15), where the function returns fifteen. Hence the result is fifteen.