Sub-Teams‎ > ‎Programming‎ > ‎

A Plus B (Hard)

This dmoj puzzle involves simply adding together two numbers, and it is worth 15 points!

The challenge is that the numbers are signed and can be very large (up to 100,000 digits each), and there is a time limit.

Approach

The secret to solving the A plus B puzzle is the management of large numbers.

Try creating a BigNumber class to manage the big numbers.  This class could parse the string into an array of longs containing 18 digits each (since a long can hold a 19 digit number).  By adding arrays of 18 digit numbers, and allowing 1 digit for carry, the solution will be 18 times faster than adding each digit individually.

Hint: keep the sign of the number separate from the scale value of the number

Hint: StringBuilder is more than 50 times faster than manipulating Strings.  Manipulate all strings using the StringBuilder class instead of just plain old Strings.

Solution

When adding two numbers of the same sign, add the absolute value of the numbers and set the sign based on the sign of the numbers (carry where appropriate).

When adding two numbers of different signs, then subtract the absolute value of the smaller number from the absolute value of the larger number and set the sign based on the larger number.  A routine is needed to compare the absolute values of two BigNumbers and know which way to do the subtraction (and the borrow), and then set the sign based on the larger number.

An example java solution can be found here, but you should not need it!