During the round I got 6 WA for problem A. This is my solution 3804729.
I was using math pow function for generating a number from it's digits. Simply like this - pow(10, j), 0 < j < number of digits.
After the contest I found that each time pow was returning floor results. So I used for loop instead of pow and it worked 3804738.
And most frustrating thing is that first solution is giving correct result for each test case on my PC. Can anyone please tell me why pow function failed in this case?
You should notice that you can only remove the last digit and the one before it. Math is a great solution if we can remove anyone all digits.
Actually problem is not about removal of digits, it is about failure of power function. I am removing last digit by this 'n/10' and using power function to remove the digit before last.
ok fine…… i misunderstand sth and got it now
The
powfunction works as it should. It doesn't compute precise integer powers, but rather a floating point result, which may differ slightly from the true value.Okay, got it!
Then what will be the alternative for
powfunction to calculate integer powers? for loop is not always efficient.There is no standard alternative. A
forloop is good enough, because with standard integer types you can't do too many iterations without overflow. If you use long arithmetic or have to compute large powers modulo something, then use binary exponentiation: https://en.wikipedia.org/wiki/Exponentiation_by_squaringFast exponentiation or precalculation should work for you. The latter, for example, can help in polynomial hashing.
Here is an example of non-recursive implementation of binary exponentiation:
Instead of pow function , you should use powf function and you will then see that it will work absolutely fine..