When i used built-in Log2 in python library i got WA for second subtask and But when I manually calculated log2 i got correct AC
1 Like
I think the problem is due to approximation. For small testcases it may seem to work. But for larger values the error may be too high to ignore (ie answer may vary by ± 1 index position) , thereby rendering WA.
i checked for 10^18 from both files i got 7 in both cases
Even tried Both C++ and Python
fails for some inputs between 1 \leq 10^{18} not checking just for 10^{18} gets AC. WA due to precision errors bro
I write it as log2((long double)n) in c++ . It showed AC.
2 Likes
I had the same issue in Python while using math.log2() , I then used bit_length() -1
can you please elaborate?
Try log2(2**59 - 1) in Python, it yields 59.0
Likewise, in C++ int(log2(2^59 - 1)) yields 59
Log2 isn’t very reliable for ‘exact’ computations. It is better to implement it manually for the specific use cases required in your problem.
4 Likes
Be careful with log2() !!!! - Codeforces here is the detailed explanation for those who use it in C++
2 Likes
Ohh I got it
> Be careful for log2
basically bit_length() returns the position of the highest set bit i.e. the length of the binary representation of the number (i.e. log2)
refer to this link logarithm - Log to the base 2 in python - Stack Overflow
1 Like
Check for this:
1
18014398509481983
The output should be 9, I think yours should give 2.
2 Likes
Yes Built-in Log Program is giving answer 2
Yes, the log function is losing precision for large numbers. That’s the reason for WA. This link explains the problem for C++, but I think the reason for Python should be the same.
Faced the same problem with log2(n) but log2l(n) will work fine in c++…
Yes, after many WA. I did the same thing and got AC.
that is log2((long double)n).
reason:
both long long int and double are of same size 8 bytes.
but when we pass long long int in log2 function then it will implicitly convert it into double.
and when large long long int converted into double it will lose some data because in double it will also store floating digits after this decimal point.
So, after type casting long long int into long double(12 bytes)…data of large number also not lossed…
This is my first contribution…hope it will be helpful
3 Likes