Vfrdtyky

I need to add two very large numbers without using BigInteger. I am taking two string parameters but the below code only works with strings of equal length otherwise it throws IndexOutOfBoundsException. How can I fix that by adding big numbers irrespective of their length?

public static String add(String a, String b) {

    int carry = 0;

    String result = "";



    for (int i = a.length() - 1; i >= 0; i--) {

      int digitA = a.charAt(i) - 48;

      int digitB = b.charAt(i) - 48;



      int resultingNumber = digitA + digitB + carry;

      if (resultingNumber >= 10) {

        result = (resultingNumber % 10) + result;

        carry = 1;

      } else {

        result = resultingNumber + result;

        carry = 0;

      }

    }

    if (carry > 0) {

      result = carry + result;

    }

    return result;

}

You can prepend the shorter string with zeros to make it match the length of the other number:

private static String leftPad(String s, int length) {

    if (s.length() >= length)

        return s;



    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < length - s.length(); i++)

        sb.append("0");



    return sb.toString() + s;

}



public static String add(String originalA, String originalB) {



    int maxLength = Math.max(originalA.length(), originalB.length());

    String a = leftPad(originalA, maxLength);

    String b = leftPad(originalB, maxLength);



    ... rest of your method

There is no need to pad any of the parameters with zeroes. Also, for better performance, don't use String + String.

Create a char for the result. Since the result can be 1 longer than the longest input, create it at that size.

Then iterate from end of input strings, setting each character in the result.

Then eliminate any leading zeroes, resulting from inputs not overflowing or from inputs having leading zeroes.

Finally, create a String from the char using the String(char value, int offset, int count) constructor.

Like this:

public static String add(String a, String b) {

    int i = a.length();

    int j = b.length();

    int k = Math.max(i, j) + 1; // room for carryover

    char c = new char[k];

    for (int digit = 0; k > 0; digit /= 10) {

        if (i > 0)

            digit += a.charAt(--i) - '0';

        if (j > 0)

            digit += b.charAt(--j) - '0';

        c[--k] = (char) ('0' + digit % 10);

    }

    for (k = 0; k < c.length - 1 && c[k] == '0'; k++) {/*Skip leading zeroes*/}

    return new String(c, k, c.length - k);

}

Test

public static void main(String args) {

    test("1234", "2345");   // test equal-sized inputs, no carry-over

    test("12345", "12345"); // test equal-sized inputs, with carry-over

    test("54321", "54321"); // test equal-sized inputs, longer result

    test("99999", "99999"); // test max result

    test("5", "1234");      // test odd-sized inputs, no carry-over

    test("5", "12345");     // test odd-sized inputs, with carry-over

    test("1", "99999");     // test with a carry-over to longer result

    test("001", "00002");   // test leading zeroes in input are eliminated

    test("000", "00000");   // test leading zero removal leaves 1 zero

}

public static void test(String a, String b) {

    // Test add is commutative, i.e. a+b = b+a

    System.out.printf("%s + %s = %s = %s%n", a, b, add(a, b), add(b, a));

}

Output

1234 + 2345 = 3579 = 3579

12345 + 12345 = 24690 = 24690

54321 + 54321 = 108642 = 108642

99999 + 99999 = 199998 = 199998

5 + 1234 = 1239 = 1239

5 + 12345 = 12350 = 12350

1 + 99999 = 100000 = 100000

001 + 00002 = 3 = 3

000 + 00000 = 0 = 0

You can left pad with zeroes the strings like this:

    int longestString = Math.max(a.length(), b.length());

    a = String.format("%1$" + longestString + "s", a).replace(' ', '0');

    b = String.format("%1$" + longestString + "s", b).replace(' ', '0');

This will add leadings spaces to fill the "gap" and then replace them with zeroes.

Class:

public class Mission09 {

    public static void main(String args) {

        System.out.println(add("1", "1333"));

    }



    public static String add(String a, String b) {

        int carry = 0;

        String result = "";



        int longestString = Math.max(a.length(), b.length());



        a = String.format("%1$" + longestString + "s", a).replace(' ', '0');

        b = String.format("%1$" + longestString + "s", b).replace(' ', '0');





        for (int i = a.length() - 1; i >= 0; i--) {

            int digitA = a.charAt(i) - 48;

            int digitB = b.charAt(i) - 48;



            int resultingNumber = digitA + digitB + carry;

            if (resultingNumber >= 10) {

                result = (resultingNumber % 10) + result;

                carry = 1;

            } else {

                result = resultingNumber + result;

                carry = 0;

            }

        }

        if (carry > 0) {

            result = carry + result;

        }

        return result;

    }



}

I/O:

System.out.println(add("1", "1333"));

1334

System.out.println(add("12222", "1333"));

13555