same formula but 1 get wrong answer

help
1

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

2

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

3

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