Find difference b/w two code

CodeChef-DSA-learners
1

problem : CodeChef: Practical coding for everyone
submitted code : CodeChef: Practical coding for everyone
partial submitted code : CodeChef: Practical coding for everyone

I am unable to find the difference b/w these two solutions. What is the problem in that “partially submitted code”.
When I replaced code from line no. 17 to 19 (in partial submitted code) by line no. 20 to 25 (in submited code) then newly formed solution got submit.
What is the basic difference?
Please help me!

2

https://www.diffchecker.com/uTUTzTZ5

Consider the test input:

1
8589934592

The partially-correct version does a shift of the int 1 (so the result will be an int) by 33, which results in an int overflow.

That could be fixed by doing:

x = (static_cast<lli>(1) << x) - 1;

instead, though the use of the floating-point log2 may or may not cause problems due to lack of precision.

The correct solution does the shift manually on a variable of type lli, so does not overflow.

Edit:

Yep, even after fixing the overflow, the use of log2 causes a failure on the following test input:

1
576460752303423487
3 Likes
3

@ssjgz thanks!

1 Like
4

You could have used the following tricks to spot the overflow in the partially-correct solution:

4 Likes