I was recently given a programming puzzle that I cannot for the life of me find a satisfactory answer for: compute the sum of two arbitrarily large integers given by strings, where the second integer may be negative. This was to be done in Java without using any of the BigInteger
, BigNumber
etc. classes.
My initial approach was the following in pseudocode:
My algorithm works fine for positive numbers, but gives wildly incorrect results for negative numbers. I've tried to work this out on paper but I just don't seem to be able to understand how to do subtraction digit by digit.
My current algorithm for steps 4 and 5 are as follows:
int[] result = new int[number1.length];
int carry = 0;
for(int i = number1.length - 1; i >= 0; i--) {
int newDigit = (negative ? number1[i] - number2[i] : number1[i] + number2[i]);
newDigit += carry;
if (newDigit >= 10) {
carry = 1;
newDigit -= 10;
} else if (newDigit < 0) {
carry = -1;
newDigit += 10;
} else {
carry = 0;
}
result[i] = newDigit;
}
// Convert result back into a string.
String resultString = intArrayToString(result);
// Apply carry.
if(carry == 1) {
return "1" + resultString;
} else if(carry == -1) {
return "-" + resultString;
} else {
return resultString;
}
If the sign is negative and number2 is larger than number1 you can simply swap those integer arrays.
You can try something like this:
boolean swap = false;
for(int j = 0; j < number1.length && negative; j++){
if(number2[j] > number1[j]){
swap = true;
int temp[] = number1;
number1 = number2;
number2 = temp;
break;
} else if(number1[j] > number2[j]){
break;
}
}
int[] result = new int[number1.length];
int carry = 0;
for(int i = number1.length - 1; i >= 0; i--) {
int newDigit = (negative ? number1[i] - number2[i] : number1[i] + number2[i]);
newDigit += carry;
if (newDigit >= 10) {
carry = 1;
newDigit -= 10;
} else if (newDigit < 0) {
carry = -1;
newDigit += 10;
} else {
carry = 0;
}
result[i] = newDigit;
}
// Convert result back into a string.
String resultString = "";
for(int j = 0; j <result.length; j++){
resultString += (result[j] + "");
}
// Apply carry.
if(carry == 1) {
return "1" + resultString;
} else if(carry == -1 || swap) {//if swap is set sign is -
return "-" + resultString;
} else {
return resultString;
}