I got a WA on this code for this problem . I read a few accepted codes and I’ve done exactly the same thing in my code! Can someone point out where I’m going wrong?
I’m posting a cleaner version of my submission here:
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#define ll long long
using namespace std;
ll gcd(ll a, ll b);
int check_if_powerTwo(ll n);
int isPowTwoDiff(ll n);
int main()
{
ll T;
cin >> T;
while(T--){
ll p, q;
cin >> p >> q;
ll greatest_factor = gcd(p,q);
// Reduce p/q
p = p/greatest_factor;
q = q/greatest_factor;
if(p >= q)
p = p - q; //reduce by 1
if(p > q)
cout << "NO" << endl; // p/q > 2
else if(p == q || p == 0)
cout << "YES" << endl; // p/q = 1 or 2
else {
// if p = 1: q = 2^k - 1 OR q = 2^j(2^k-1) , for some j,k
if(p == 1) {
if(check_if_powerTwo(q+1) || isPowTwoDiff(q))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
// else if p = 2^i: q = 2^k - 1
else if(check_if_powerTwo(p)){
if(check_if_powerTwo(q+1))
cout << "YES"<< endl;
else
cout << "NO" << endl;
}
else
cout << "NO" << endl;
}
}
return 0;
}
ll gcd(ll a, ll b)
{
ll rem;
if(a > b){
ll temp = a;
a = b;
b = temp;
}
while((rem = b % a)) {
b = a;
a = rem;
}
return a;
}
int check_if_powerTwo(ll n)
{
if(n & (n-1))
return 0;
else
return 1;
}
// is n = 2^i - 2^j
int isPowTwoDiff(ll n)
{
if(n == 0)
return 0;
while(n % 2 == 0)
n = n / 2;
return(check_if_powerTwo(n + 1));
}