[Community Puzzle] The Lucky Number

Struggled through this puzzle and discovered in a hard way that the Math library in Java will sometimes produce a precision error when producing long integer results.

long n = (long)Math.pow(9, 17)

n value given by java is 16677181699666570
using a calculator to cross check, 9^17 is 16677181699666569

Math.pow deals with double. It loses precision when double is cast to long. I believe many other languages have a similar limitation, causing strange errors when solving extreme problems.

It’s not anything to do with the casting to long, the precision is lost as soon as you use the double type. The IEEE standard for a double precision float (https://en.wikipedia.org/wiki/Double-precision_floating-point_format) cannot actually represent that value as it only has 53 bits of precision (9^17 requires 54 bits to represent exactly).

Doing the calculation of 9^17 manually inside a long variable will work correctly as it never gets converted into a double.


I wrote some logic in java to solve this problem but I am unable to run last 2 test cases because of time limit.

In 2 Seconds,to run these 2 test cases it is some what difficult for me.
Test Cases: 64-bit Number (92871036442 3363728910382456)
Biggest Number(1 1000000000000000000)

Did anyone solve this problem?
Please let me know. It will be helpful.


I passed all the tests in the IDE but my code doesn’t pass the 4th and 5th validators.

EDIT: I found the problem. Please can someone add the following tests in the IDE:
input: 5999 6000
output: 1

input: 7148 8875
output: 1018

These two inputs did not give me the good results with my old code.