Add Two Huge Numbers (Strings)
Problem
Two non-negative numbers are given as digit strings on two lines. They can have up to 200 digits. Print their sum. Do not use BigInteger or BigInt. Add the digits by hand, as on paper.
Constraints
- 0 <= each number < 10^200, no leading zeros except 0 itself
Examples
Input
999 1
Output
1000
Solutions
We do school addition: add the last digits, write the last digit of the total, and carry the rest. The loop ends when both numbers and the carry are finished.
/*
* Problem : Add two big numbers given as text.
* Input : Two lines with digits.
* Output : The sum.
* Approach: Add digit by digit with a carry.
* Time : O(n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String solve(String a, String b) {
// Step 1: Start at the last digit of both numbers. The carry starts at 0.
StringBuilder result = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
// Step 2: Continue while there are digits left or a carry is left.
while (i >= 0 || j >= 0 || carry > 0) {
// Step 3: Take the digits (0 when a number is already finished) and add the carry.
int digitA = i >= 0 ? a.charAt(i) - '0' : 0;
int digitB = j >= 0 ? b.charAt(j) - '0' : 0;
int total = digitA + digitB + carry;
// Step 4: The last digit of the total goes to the result. The other part is the new carry.
result.append(total % 10);
carry = total / 10;
i--;
j--;
}
// Step 5: We built the result from right to left, so reverse it.
return result.reverse().toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String a = scanner.next();
String b = scanner.next();
System.out.println(solve(a, b));
}
}
Hints (1)
- What is the largest carry when adding two digits?