Like the other answers before mine, the problem is about big values of exp n. If you took pen and paper and try for example to multiplicate 1331 (\$11^3\$) and 11 to obtain number 14641 (\$11^4\$) you do in this way:
1331 x
11
-------
1331 +
1331
-------
14641
So basically if you have \$11^n\$ and you want to calculate \$11^{n+1}\$ it can be calculated with the sum of the \$11^n\$ and \$11^n * 10\$. To avoid problem due to the dimensions of numbers you can write the the numbers with strings. In the case of number 1331 we can use sum the strings 01331
and 13310
and calculate string 14641
.
I defined a class called PowerOfEleven
and a main method containing the tests below:
public class PowerOfEleven {
private static String ELEVEN = "11";
private static String ZERO = "0";
private static String ONE = "1";
public static void main(String[] args) {
assertEquals(calculatePower(0), "1");
assertEquals(calculatePower(1), "11");
assertEquals(calculatePower(2), "121");
assertEquals(calculatePower(3), "1331");
assertEquals(calculatePower(4), "14641");
assertEquals(calculatePower(5), "161051");
assertEquals(calculatePower(6), "1771561");
}
}
The method calculatePower
calculates for every n the number \$11^n\$ using the sum of strings like when you use pen and paper:
public static String calculatePower(int n) {
if (n == 0) { return ONE; }
String number = ELEVEN ;
for (int i = 1; i < n; ++i) {
String first = ZERO + number;
String second = number + ZERO;
number = sum(first, second);
}
return number;
}
I'm adding the strings putting one zero before the first string and another zero after the second string, so for example for number 1331 you obtain strings 01331
and 13310
.
I defined a method for the sum of the strings like below:
private static String sum(String s1, String s2) {
final int n = s1.length();
char[] arr1 = s1.toCharArray();
char[] arr2 = s2.toCharArray();
StringBuilder result = new StringBuilder();
int remainder = 0;
for (int i = n - 1; i >= 0; --i) {
int firstDigit = Character.getNumericValue(arr1[i]);
int secondDigit = Character.getNumericValue(arr2[i]);
int value = firstDigit + secondDigit + remainder;
remainder = 0;
if (value >= 10) {
value = value - 10;
remainder = 1;
}
result.append(Character.forDigit(value, 10));
}
if (remainder > 0) {
result.append(remainder);
}
return result.reverse().toString();
}
The method uses a StringBuilder
object to store the result : when you sum the digits of the two strings starting from the end you obtain a new digit and a remainder that can be 0 or 1. The new digit obtained from the sum is appended at the of the StringBuilder
, so you have to reverse the StringBuilder
result to obtain the real value.
Note : @slepic idea of using Pascal triangle if implemented simplifies my idea of sum of strings and surely improves performance.