Euclid's worst-case step count

MediumProgramming & DSA~4m

The Euclidean algorithm computes $\gcd(a,b) = \gcd(b,\, a \bmod b)$ , repeating until the second argument is $0$ . Count the number of $\bmod$ (remainder) operations performed for $\gcd(34, 21)$ .

Show hints (2)+

$34$ and $21$ are consecutive Fibonacci numbers - the worst case.
Trace $\gcd(b, a\bmod b)$ until the remainder is $0$ ; count the $\bmod$ s.

Answer

Reveal answer →

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Prop Trading, Systematic & Data-Driven Trading

Euclid's worst-case step count

Answer

Related questions