Orejano - 6 months ago 211

Java Question

I had the following scenario today on an Interview for a Developer Job, this was one of the questions, and only one I fail to answer.

Concatenate the number N N times and then calculate his Modulus by 2017.

For example: for N=5 the number will be 55555 and the result will be Mod(55555,2017) = 1096 for N=10 the number will be 10101010101010101010 and the result Mod(10101010101010101010,2017) = 1197

Now the Number I had to calculate was 58184241583791680. The only hint I got was that the result of 58184241583791680 concatenated 58184241583791680 times modulus 2017 is a 4 digit number.

I posted this question on math.stackexchange and I got a mathematical approach to this problem, other than brute force.

I wrote the following code in JAVA

`import java.math.BigDecimal;`

import java.math.BigInteger;

import java.math.MathContext;

public class Puzzle {

final static BigInteger M = new BigInteger("2017");

public static void main(String [ ] args) {

for (long n : new long[] { 1L, 2L, 5L, 10L, 20L }) {

System.out.println(n + " --> " + bruteForce(n) + " --- " + formulaV2(n));

}

}

private static BigInteger bruteForce(long n) {

String s = "";

for (long i = 0; i < n; i++) {

s = s + n;

}

return new BigInteger(s.toString()).mod(M);

}

private static BigInteger formulaV2(long n) {

String aux = String.valueOf(n);

long L = aux.length();

long K = n;

double op1 = Math.pow(10,L*K);

BigDecimal minus1 = new BigDecimal(1);

BigDecimal p1 = new BigDecimal(op1).subtract(minus1);

double op2 = Math.pow(10,L);

BigDecimal p2 = new BigDecimal(op2).subtract(minus1).pow(-1,MathContext.DECIMAL64);

BigDecimal R = new BigDecimal(n).multiply(p1).multiply(p2);

R = R.setScale(0,BigDecimal.ROUND_UP);

BigInteger ret = R.toBigInteger();

return ret.mod(M);

}

}

I'm using BigInteger and BigDecimal because I want to get the value of really big numbers (16+ digits).

The bruteForce method will simply concatenate the number inside a loop, and the formulaV2 method will use the formula from the question asked in the math forum.

bruteForce method is just for validation.

However the formula method works well for N<10 but no for N>=10. At N=10 I'm getting incorrect results.

The coding seems to be consistent (to me at least, maybe there is something I'm missing) with the formula provided, and the formula is correct (I checked in Wolfram Alpha).

My guess is that I have precision problems, maybe BigDecimal is not the proper object in this case?.

Answer

This is a problem:

```
double op1 = Math.pow(10,L*K);
```

for example, when `n = 20`

, `L*K = 40`

, and `op1 = 10000000000000000303786028427003666890752`

. As for why, the usual floating point business: it's the closest it could get. There is no `double`

with a value of exactly 1E40.

`op1`

won't print like that (you'll see 1E40 and think all is fine), but it will convert like that. Then you're going to use `BigDecimal`

which is fine (though odd), it already went wrong before that.

I assume you used `BigDecimal`

*because* you converted from a `double`

, otherwise you would have used `BigInteger`

. Just use `BigInteger.pow`

instead of `Math.pow`

and it may work (it fixes this issue, if there's anything else I haven't noticed but I can't promise it will work).

`Math.pow(10,L)`

on the other hand shouldn't be a problem, because `L`

is low enough .. for now. You might as well change that too and have it work for large `L`

though.