Subtracting two integers digit by digit

Question

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:

1. If the first character of the second string is '-' then set the subtraction flag.
2. Convert each string to an array of integers, one for each digit.
3. Extend the shortest array and left-pad with zeros so both arrays are the same size.
4. 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.
5. 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;
}

Answer 1

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;
}

Answer 2

If the last carry is -1, then it means you have to add -1 * 10^(number of digits) to the answer.

 01
-10
---
 91

And Carry = -1. Hence you have to add -100 to 91 to get the actual answer.

The solution is simply to subtract the smaller number from the larger number and then add the sign accordingly.

Answer 3

You can wrap it with:

if(A>=B):
    calculate A-B
else:
    calculate -(B-A)

Answer 4

Make sure when doing subtraction that the larger number is in number1 or else you will get odd answers. If needed switch number1 and number2 and account for the negative as needed. Otherwise looks okay to me.

So for example 1 + -10 should be 10 - 1, and the negative of that result, -9.

Answer 5

Well you could just switch +/- sign.

For example if num1 = 1, num2=-10, instead of doing (1-10) and get -9, you may try do -(10-1) instead. cause it seems your algo could perform properly if num1=10, and num2=-1.

So basically you would switch num2 with num1, if it has larger magnitude than num1, and negate the end result.

* Okay someone did the code while I was commenting.