Given 2 non-negative integers a, b that range between (1 and 1e9), let c = |a - b| and after calculating c let a = b, b = c then recalculate c. what is the number of operations needed for c to reach 0. for example, first operation: a = 1 and b = 2, c = |a - b| = 1 second operation: a = 2 and b = 1, c = |a - b| = 1 third operation: a = 1 and b = 1, c = |a - b| = 0 so, we need 3 operations. note: I need a solution other than just iterating until c reaches 0 because that would result into a really bad runtime when writing it as a code.
I saw some of my friends' solutions and it all is based on generalized Euclidean theorem but with some modifications I think. but I couldn't understand.
I hope someone can simplify the solution to me and thanks in advance! <3.
Your question is about the number of steps in a subtractive Euclidean algorithm. The total number of subtractions is exactly equal to the sum of all the quotients when using the related Euclidean algorithm with divisions.