 # same formula but 1 get wrong answer

what is the difference between these 2 formulas ? (p, q, N are long type)

``````long sol = (long) ( (N-1) * q / ( 2 * fabs(q-p) ) +1 )
long sol = (long) ( (N-1) / ( 2.0 * fabs(q-p) / q ) +1 ) ;
``````

For the full context, I’m solving the problem Useless Clocks, the second one gives me wrong answer

It’s because the first equation is divided by 2*fabs(q-p) and then 1 is added to the result while in the second equation you are dividing by ( 2 * fabs(q-p)/q) + 1

Run this:

``````#include <iostream>
#include <cmath>

using namespace std;

int main()
{

while (true)
{
const long N = 1 + rand() % 1'000'000;
const long q = 1 + rand() % 10'000;
const long p = (rand() % 2 ? -1 : 1) * rand() % 1'000'000;
const auto K = static_cast<double>(p) / q;
if (-100 <= K && K <= 100)
{
long sol1 = (long) ( (N-1) * q / ( 2 * fabs(q-p) ) +1 );
long sol2 = (long) ( (N-1) / ( 2.0 * fabs(q-p) / q ) +1 ) ;
if (sol1 != sol2)
{
cout << "N: " << N << " p: " << p << " q: " << q << endl;
cout << "sol1: " << sol1 << " sol2: " << sol2 << endl;
return 1;
}
}

}
}

``````

Edit:

No, that’s not correct; the discrepancy can still be observed if we remove the “+1” entirely. In fact, we can strip the two formulae down to e.g.

`````` long sol = (long)((N - 1) * q / (2.0 * fabs(q - p)));
``````

vs

`````` long sol = (long)((N - 1) / (2.0 * fabs(q - p) / q));
``````

and still find a mismatch.

1 Like