O(n) will not pass. i tried already.
Hi, Please share the link of the problem.
x = x/GCD(x,y);
y = y/GCD(x,y);
and then
min( floor(w/x), floor(h/y) )
will this work?
No , this will also give wrong answer to many cases.
This got AC.
g=__gcd(x,y);
x/=g;
y/=g;
ans=min(w/x,h/y);
Still not passes fully got 54 points out of 100
Bro i give the link in above comment , u can submit and tell after u got full marks.
I have already submitted and got full marks.
https://www.hackerrank.com/contests/procode-final-round-avengers-theme/challenges/captains-shield-1/submissions
Then Please share ur full code bcz i applied everything :(
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
int gcd(int a,int b){if (a==0)return b;return gcd(b%a,a);}
signed main()
{
int w,x,h,y,g,c=0;
cin>>w>>h>>x>>y;
g=__gcd(x,y);
x/=g;
y/=g;
c=min(w/x,h/y);
cout<<c;
return 0;
}Thanks, But why my code fails then, is __gcd(a,b) is different from Euclidean algo.
I checked… codes passes without euclidian algo too !!!
Can you please share your code ?
#include
#include
#include
#include
#include
using namespace std;
int main() {
long long int w,h,x,y;
cin>>w>>h>>x>>y;
if(y>h || x>w)
cout<<0;
else
cout<<(min((w/__gcd(x ,y)), (h/__gcd(x ,y))));
return 0;
}
You have divided by gcd(x,y) which is wrong…
then please explain ur code wrt to problem how it works. mathematically
here is another question in which i got 91 marks. HELP!
https://www.hackerrank.com/contests/procode-final-round-avengers-theme/challenges/tony-stark-and-perfect-equipment
We had to find all numbers of form (a,b) which were having same ratio as (x,y).
so first we reduced (x,y) to the simplest ratio by dividing them by their gcd.
Now, simply we pick the min of w/x and h/y.
even I was wondering what’s the difference between the two codes