Repeated subtraction among two numbers - GeeksforGeeks
Given a pair of positive numbers x and y. We repeatedly subtract the smaller of the two integers from greater one until one of the integers becomes 0. The task is to count number of steps to before we stop (one of the numbers become 0).
Read full article from Repeated subtraction among two numbers - GeeksforGeeks
Given a pair of positive numbers x and y. We repeatedly subtract the smaller of the two integers from greater one until one of the integers becomes 0. The task is to count number of steps to before we stop (one of the numbers become 0).
A simple solution is to actually follow the process and count the number of steps.
A better solution is to use below steps. Let y be the smaller of two numbers
1) if y divides x then return (x/y)
2) else return ( (x/y) + solve(y, x%y) )
1) if y divides x then return (x/y)
2) else return ( (x/y) + solve(y, x%y) )
// Returns count of steps before one// of the numbers become 0 after repeated// subtractions.int countSteps(int x, int y){ // If y divides x, then simply return // x/y. if (x%y == 0) return x/y; // Else recur. Note that this function // works even if x is smaller than y because // in that case first recursive call exchanges // roles of x and y. return x/y + countSteps(y, x%y);}