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. ApproachThe 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. SolutionWhen 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! |
Sub-Teams > Programming >