"EQUIVALENT NUMBERS" STARTERS 58 (A faster solution than the editorial)

tutorial
, ,
1

After the end of the contest I saw that in the editorial and most of the contestants used prime factorization which leads to a time complexity of O(sqrt(max(A, B)) , but I did a much faster solution in O(1) (it got accepted).
My solution:
we need to find if there are two positive integers X and Y such that A^X = B^Y.
Let’s break this down like the following:
A^X = B^Y ==> exp(X * log(A)) = exp(Y * log(B))
==> X * log(A) = Y * log(B)
==> X / Y = log(B) / log(A)
X and Y being integers means that we need to check if log(B) / log(A) is a rational number or not, here is an algorithm to approximate that:

bool is_rational(long double x) {
    x = abs(x);
    for (int i = 0; i < 20; ++i) {
        const auto a = floor(x);
        if (x - a < 1e-8)
            return true;
        x = 1 / (x - a);
    }
    return false;
}

so we output YES if it’s rational and NO otherwise, this solution is O(1) time complexity.
I hope I explained my solution very well, and if there is something wrong about it please feel free to discuss it.
my submission: CodeChef: Practical coding for everyone

2

I also reached this solution but I couldn’t write the checking rational number algo as only 1 min was left in time I started late :frowning: thanks for the solution I will save this logic in my mind now

2 Likes
3

This is a bit fishy, because any number representable by the long double data type is technically rational (excluding special values, such as Inf or NaN). That’s because internally this data type contains a signifacand part and an exponent part. The significand part represents the integer numerator of a fraction and the exponent part represents the integer (power of 2) denominator. Thus any irrational number always gets rounded to some rational number when it is assigned to a long double variable.

1 Like
4

as i said it’s just an approximation, and as you can see it got accepted, also i know that memory is a no infinite to hold an irrational number that’s why we approximate everything.
Thank you for your comment I appreciate it.

5

as you can see it got accepted

Looks like the test cases are just weak. Try the following input:

7
3 483197
9 483197
10 79076
10 790760
19 14789
19 280991
24 734341

Your solution reports YES for all of these cases. And the @utkarsh_adm’s solution from the editorial reports NO.

2 Likes
6

I knew that there can be edge cases bcs its an approximation , thank u for pointing it out , the test cases were indeed weak bcs when i submitted i was expecting a WA :stuck_out_tongue:

7

using a for loop with exit condition: i < ln n makes your function run in O(log n) not O(1).

1 Like