The user will input 2 integers, x and y, using standard input. You need to calculate the remainder of x modulo y (x % y).
Now, here is the problem:
0 <= x <= 10^100000, (this is "less than or equal" not an arrow). 0 < y <= 100000
We are looking for optimal solution (Time Complexity).
I didn't find the answer on Stackoverflow, so after finding the solution I thought that I should pose this question here for future reference and to see if there are better ways.
BigInteger has the divideAndRemainder(...) method, one that returns a BigInteger array, the first item the division result, and the second, the remainder (which is what mod really does in Java).
Update
Including comment by Mark Dickinson to other answer:
There's a much simpler linear-time algorithm: set acc to 0, then for each digit d in x in turn (left to right), convert d to an integer and set acc = (acc * 10 + d) % y. Once the digits are consumed, acc is your result.
Implemented all 3 algorithms as described:
private static int testMarkDickinson(String x, int y) {
int acc = 0;
for (int i = 0; i < x.length(); i++)
acc = (acc * 10 + x.charAt(i) - '0') % y;
return acc;
}
private static int testHovercraftFullOfEels(String x, int y) {
return new BigInteger(x).divideAndRemainder(BigInteger.valueOf(y))[1].intValue();
}
private static int testMrM(String x, int y) {
String s = x;
while (s.length() >= 7) {
int len = Math.min(9, s.length());
s = Integer.parseInt(s.substring(0, len)) % y + s.substring(len);
}
return Integer.parseInt(s) % y;
}
Testing with seeded random number for verifiable test (didn't want to hardcode a 98765 digit number):
public static void main(String[] args) {
Random r = new Random(98765);
char[] buf = new char[98765];
for (int i = 0; i < buf.length; i++)
buf[i] = (char)('0' + r.nextInt(10));
String x = new String(buf);
int y = 98765;
System.out.println(testMarkDickinson(x, y));
System.out.println(testHovercraftFullOfEels(x, y));
System.out.println(testMrM(x, y));
long test1nano = 0, test2nano = 0, test3nano = 0;
for (int i = 0; i < 10; i++) {
long nano1 = System.nanoTime();
testMarkDickinson(x, y);
long nano2 = System.nanoTime();
testHovercraftFullOfEels(x, y);
long nano3 = System.nanoTime();
testMrM(x, y);
long nano4 = System.nanoTime();
test1nano += nano2 - nano1;
test2nano += nano3 - nano2;
test3nano += nano4 - nano3;
}
System.out.printf("%11d%n%11d%n%11d%n", test1nano, test2nano, test3nano);
}
Output:
23134
23134
23134
8765773
1514329736
7563954071
All 3 produced same result, but there's a clear difference in performance, and Mr. M's "better solution" is the worst of them all.
The solution that is better than BigInteger is the following:
1- Read the x as String and y as an integer.
2- Cut the first 9 characters from the left of x and convert them to integer i.
3- calculate i % y and append it to the beginning of x.
4- repeat from 2 until the x string is less than 7 (max length of int - max length of divider).
5- concatenate s with what is left of x and calculate the modulus.
This solution is not constrained to any integer length.
