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:
- If the first character of the second string is '-' then set the subtraction flag.
- Convert each string to an array of integers, one for each digit.
- Extend the shortest array and left-pad with zeros so both arrays are the same size.
- Loop through each index of the arrays (from least significant digit to most significant digit) performing the addition/subtraction and using a carry to carry the overflow to the next digit.
- Check the carry to add any last digits.
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;
}
1
and number2 is-10
, my current algorithm gives-91
. – DanielGibbsn
where 10^n is a bit less than the largest value of your integer datatype (eg.int
). – Superbest