#### Concepts Used:

Mathematics

#### Difficulty Level:

Medium

#### Problem Statement (Simplified):

Perform following operations until one number becomes 0 and print the total number of operations.

1) Subtract`larger number`

from`smaller number`

.

2) Replace the`larger number`

by difference and repeat the steps until any one of them becomes 0.

**See original problem statement here**

#### Test Case:

```
Input:
1
5 14
Output:
6
Explanation:
Lets solve this problem iteration by iteration :
1st iteration :
ba, so b = b - a = 13 - 5 = 8 and a = 5
2nd iteration :
ba, so b = b - a = 8 - 5 = 3 and a = 5
As ab now, so we swap both, after swapping, a = 3 and b = 5
3rd iteration :
ba, so b = b - a = 5 - 3 = 2 and a = 3
As ab now, so we swap both, after swapping, a = 2 and b = 3
4th iteration :
ba, so b = b - a = 3 - 2 = 1 and a = 2
As ab now, so we swap both, after swapping, a = 1 and b = 2
5th iteration :
ba, so b = b - a = 2 - 1 = 1 and a = 1
6th iteration :
b=a, so b = b - a = 1 - 1 = 0, as b becomes 0, we print number of total iterations which resulted this, hence we achieved it at 6th iteration, so our answer is 6.
```

#### Solving Approach :

Bruteforce Approach:

1) We start a while loop and perform above-said operations one by one, and exits when any of number becomes

`0`

.

2) We also count number of times while loop ran, after while loop end, we print the number of loops.

3) This approach takes longer times to run for larger inputs, as decreasing larger number by smaller number again and again takes large time. Its time complexity is`O(M)`

, where`M`

is the greatest number of the two inputs. We can short the time of running by using mathematics which will be seen in next approach.

Efficient Approach:

1) When we get two numbers there can be two possible cases according to the fundamentals of data structures in c++:

1)IfCase 1:`larger number`

is divisible by`smaller number`

, then after steps any of number becomes 0.

2)IfCase 2:`larger number`

is not divisible by`smaller number`

, then after steps`smaller number`

becomes`larger number`

, and`smaller number`

is replaced by (`larger number`

%`smaller number`

).

2) We print the final steps after one number becomes 0.

#### EXAMPLE:

Case 1: If one number is divisible by another

Let’s take`a=25`

and`b=5`

, if we continously subtract`a`

from`b`

,`b`

becomes zero after`5`

iterations i.e. ᵗʰ iteration, we can visualise this as,

`1ˢᵗ`

iteration:

`b = b - a = 25 -5 = 20`

, hence`a = 5, b = 20`

`2ⁿᵈ`

iteration:

`b = b - a = 20 -5 = 15`

, hence`a = 5, b = 15`

`3ʳᵈ`

iteration:

`b = b - a = 15 -5 = 10`

, hence`a = 5, b = 10`

`4ᵗʰ`

iteration:

`b = b - a = 10 -5 = 5`

, hence`a = 5, b = 5`

`5ᵗʰ`

iteration:

`b = b - a = 5 -5 = 0`

, hence`a = 5, b = 0`

Case 2: If no number is completely divisible by another

Let’s take`a=27`

and`b=5`

, if we contiously subtract`a`

from`b`

,`b`

is left with remainder of`b`

/{a} after`5`

iterations i.e.ᵗʰ iteration, we can visualise this as,

`1ˢᵗ`

iteration:

`b = b - a = 27 -5 = 22`

, hence`a = 5, b = 22`

`2ⁿᵈ`

iteration:

`b = b - a = 22 -5 = 17`

, hence`a = 5, b = 17`

`3ʳᵈ`

iteration:

`b = b - a = 17 -5 = 12`

, hence`a = 5, b = 12`

`4ᵗʰ`

iteration:

`b = b - a = 12 -5 = 7`

, hence`a = 5, b = 7`

`5ᵗʰ`

iteration:

`b = b - a = 7 - 5 = 2`

, hence`a = 5, b = 2`

Now, we can continue with swapped value of

`a`

and`b`

, as remainder will always be lower than`a`

, so we swap`a`

and`b`

making`a = 2`

and`b = 5`

, and we again check both cases and apply steps until one of them becomes`0`

.

#### Solutions:

#include <stdio.h> int main() { int test; scanf("%d",&test); while(test--){ int s,l; scanf("%d%d",&s,&l); int count = 0; while(s!=0 && l!=0){ count+=l/s; int temp = s; s = l%s; l = temp; } printf("%d\n",count); } }

#include <bits/stdc++.h> using namespace std; int main() { int test; cin>>test; while(test--){ int s,l; cin>>s>>l; int count = 0; while(s!=0 && l!=0){ count+=l/s; int temp = s; s = l%s; l = temp; } cout<<count<<endl; } }

import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int test = sc.nextInt(); while(test--!=0){ int s = sc.nextInt(),l = sc.nextInt(); int count = 0; while(s!=0 && l!=0){ count+=l/s; int temp = s; s = l%s; l = temp; } System.out.println(count); } } }