Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Subtracting two integers digit by digit

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;
}
like image 230
DanielGibbs Avatar asked Jan 21 '14 05:01

DanielGibbs


People also ask

What is subtracting 2-digit numbers?

Subtracting 2-Digit Numbers with and without Regrouping or Borrowing | How to Subtract Two Digit Numbers? Subtracting 2-Digit Numbers is the subtraction of one number from another number. Subtraction of Numbers is not that easy as the addition.

What is subtraction of integers?

The subtraction of integers is an arithmetic operation performed on integers with the same sign or with different signs to find the difference. Let us learn more about subtracting integers in this article. 1. 2. 3. There are certain rules to be followed to subtract two integers. Integers are complete numbers that do not have fractional parts.

How to add and subtract integers on a number line?

Adding a negative integer will be done by moving towards the left side (or the negative side) of the number line. Any one of the given integers can be taken as the base point from where we start moving on the number line. Now, let us learn how to subtract integers on a number line. The first step is to choose a scale on the number line.

How do you subtract integers with the same sign?

Step 1: First, we will change the sign of the subtrahend which is -5. This makes it 5. Step 2: Find the sum of the new integers, that is 6 + 5 = 11. Step 3: The result is 11. What is the Rule for Subtracting Integers with the Same Sign? To subtract integers with the same sign, we first change the sign of the subtrahend.


1 Answers

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;
}
like image 163
chathux Avatar answered Oct 12 '22 23:10

chathux