Subtracting two integers digit by digit

DanielGibbs picture DanielGibbs · Jan 21, 2014 · Viewed 10k times · Source

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

chathux picture chathux · Jan 21, 2014

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