What does this routine compute — Aptitude Question
What does this routine compute: For positive integers a and b, what does Mystery(a, b) return? Answer and worked solution on CodeKairo.
- Topic: Pseudocode
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 90 seconds
Question
For positive integers a and b, what does Mystery(a, b) return?
Function Mystery(Integer a, Integer b)
Integer t
While b != 0
Set t = b
Set b = a MOD b
Set a = t
End While
Return a
End FunctionOptions
- The LCM of a and b
- The GCD of a and b
- The remainder when a is divided by b
- The larger of a and b
Show the answer and the worked solution
Correct answer: B. The GCD of a and b
Worked solution
- Trace Mystery(48, 18): the pair becomes (18, 48 MOD 18 = 12), then (12, 18 MOD 12 = 6), then (6, 12 MOD 6 = 0).
- With b = 0 the loop stops and 6 is returned.
- 6 is exactly the greatest common divisor of 48 and 18, and the replacement (a, b) → (b, a MOD b) preserves the common divisors at every step. The GCD of a and b is therefore what the routine returns for any positive inputs.
Answer: The GCD of a and b.
The idea
This is Euclid's algorithm. The invariant is that gcd(a, b) = gcd(b, a MOD b), so the value survives every round and surfaces the moment b hits zero.
Shortcut. Try Mystery(4, 6): the pair goes (6, 4) → (4, 2) → (2, 0) and returns 2, which is the GCD, not the LCM 12, the remainder 4 or the larger value 6.
Common trap. "The remainder when a is divided by b" is picked by spotting a MOD b in the body and ignoring the loop, which keeps taking remainders until b reaches 0.