Help in this question (Random test question)

general
1

There are two numbers number A and number B. Your task is to make A and B equal by doing few operations.
In each operation:
If A is greater than B then reduce A by B i.e A = A - B
If B is greater than A then reduce B by A i.e B = B - A
Cost of each operation is 1. Find the total cost of making A equal to B.

Input Format:
Two spaced-seperated intergers A and B
Output:
Total cost

Sample TestCase #1:
Input : 7 9
Output : 5

Explanation:
Operation 1: B > A so B = 9 - 7 = 2
Operation 2: A > B so A = 7 - 2 = 5
Operation 3: A > B so A = 5 - 2 = 3
Operation 4: A > B so A = 3 - 2 = 1
Operation 5: B > A so B = 2 - 1 = 1
A and B are equal so we stop cost = 5

I tried two approaches for this question but both not accepted. This was asked in a random test.

2

Can you provide me the link of the question for better understanding

3

The link’s expired sorry

4

I tried solving the question and came up with the observation after trying some cases that both the numbers stops when they reach at their gcd, so basically we need to count the steps in which we can find their gcd using euclidean algorithm and count the no. of steps in which it returned us the answer. I hope this works bro.
check this code
#include<bits/stdc++.h>
using namespace std;
define ll long long
int gcd(int a, int b,int & count)
{
// Everything divides 0
count++;
if (a == 0)
return b;
if (b == 0)
return a;

// base case 
if (a == b) 
    return a; 

// a is greater 
if (a > b) 
    return gcd(a - b, b,count); 
return gcd(a, b - a,count);

}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a,b;
cin>>a>>b;
int count=0;
int ans=gcd(a,b,count);
cout<<count-1<<endl;

return 0;
}

5

It’s just an another way of writing brute force version it will be an TLE. I gave a thought and came up with this not sure if it will work.

while (a !=0 && b != 0)
{
    if(a < b) 
        swap(a,b);
    count += a / b
    a %= b
}

cout << count - 1;

We are kinda doing gcd. But with a little bit better TC

6

yeah, that is why I was asking for link, well it seems your solution might work efficiently. good luck, mate

7

Thanks, the links expired! and there were no constraints given in the question. It was just an 30 min speedrun test, so I kinda panicked because no constraints and 3 questions to solve :joy: