Add Strings
Add Strings is a easy arrays & hashing problem solved with the right to left traversal pattern.
The best approach, optimal (two pointers from the right), runs in O(max(n, m)) time and O(max(n, m)) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from pad and add up.
Problem
You are given two non-negative integers num1 and num2, each written as a string of decimal digits. Return their sum, also as a string.
The numbers can be thousands of digits long, so they do not fit in any built-in integer type. Work digit by digit instead of converting the whole strings to numbers.
Examples
Example 1
- Input
num1 = "478", num2 = "65"- Output
"543"- Why
- 478 + 65 = 543; the 8 + 5 and 7 + 6 + 1 columns both carry.
Example 2
- Input
num1 = "999", num2 = "1"- Output
"1000"- Why
- The carry runs through every column and adds a new leading digit.
Example 3
- Input
num1 = "0", num2 = "0"- Output
"0"- Why
- Zero plus zero is a single zero, not an empty string.
Constraints
1 <= num1.length, num2.length <= 10^4num1andnum2contain only the digits0-9.- Neither string has leading zeros, except the number zero itself.
- You may not convert the whole strings to integers or use a big-number library.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Pad and add | O(n²) | O(n) |
| Optimal (two pointers from the right) | O(max(n, m)) | O(max(n, m)) |
1Pad and add
O(n²)Prepending to a string copies it, so building n digits this way costs 1 + 2 + … + n character copies.O(n)The padded copies and the result each hold about n characters.Pad the shorter string with leading zeros so both have the same length, then add column by column from the right, prepending each digit to the result.
- Let n = max of the two lengths; left-pad both strings with '0' up to n.
- carry = 0. For i from n - 1 down to 0: sum = a[i] + b[i] + carry; prepend sum % 10; carry = sum / 10.
- If carry is left, prepend it. Return the result.
class Solution {
public String addStrings(String num1, String num2) {
int n = Math.max(num1.length(), num2.length());
String a = "0".repeat(n - num1.length()) + num1;
String b = "0".repeat(n - num2.length()) + num2;
String res = "";
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int sum = (a.charAt(i) - '0') + (b.charAt(i) - '0') + carry;
res = (char) ('0' + sum % 10) + res;
carry = sum / 10;
}
if (carry > 0) {
res = "1" + res;
}
return res;
}
}class Solution:
def addStrings(self, num1: str, num2: str) -> str:
n = max(len(num1), len(num2))
a = num1.rjust(n, '0')
b = num2.rjust(n, '0')
res = ""
carry = 0
for i in range(n - 1, -1, -1):
s = int(a[i]) + int(b[i]) + carry
res = str(s % 10) + res
carry = s // 10
if carry > 0:
res = "1" + res
return resclass Solution {
public:
string addStrings(string num1, string num2) {
int n = max(num1.size(), num2.size());
string a = string(n - num1.size(), '0') + num1;
string b = string(n - num2.size(), '0') + num2;
string res = "";
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int sum = (a[i] - '0') + (b[i] - '0') + carry;
res = string(1, (char) ('0' + sum % 10)) + res;
carry = sum / 10;
}
if (carry > 0) {
res = "1" + res;
}
return res;
}
};function addStrings(num1, num2) {
const n = Math.max(num1.length, num2.length);
const a = num1.padStart(n, '0');
const b = num2.padStart(n, '0');
let res = "";
let carry = 0;
for (let i = n - 1; i >= 0; i--) {
const sum = (a.charCodeAt(i) - 48) + (b.charCodeAt(i) - 48) + carry;
res = String(sum % 10) + res;
carry = Math.floor(sum / 10);
}
if (carry > 0) {
res = "1" + res;
}
return res;
}2Optimal (two pointers from the right)
O(max(n, m))Each column is handled once and appending is amortized O(1); the final reverse is linear.O(max(n, m))Only the output builder; besides it, a few integers.Walk one pointer down each string from its last digit. Each step adds the two digits (0 once a string is used up) plus the carry, and appends the last digit to a builder. The builder holds the answer backwards, so reverse it once at the end.
- i = num1.length - 1, j = num2.length - 1, carry = 0, sb = empty builder.
- While i >= 0 or j >= 0 or carry > 0: sum = carry + (digit at i or 0) + (digit at j or 0).
- Append sum % 10 to sb, set carry = sum / 10, move i and j left.
- Return sb reversed.
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += num1.charAt(i--) - '0';
if (j >= 0) sum += num2.charAt(j--) - '0';
sb.append((char) ('0' + sum % 10));
carry = sum / 10;
}
return sb.reverse().toString();
}
}class Solution:
def addStrings(self, num1: str, num2: str) -> str:
out = []
i, j, carry = len(num1) - 1, len(num2) - 1, 0
while i >= 0 or j >= 0 or carry > 0:
s = carry
if i >= 0:
s += ord(num1[i]) - 48
i -= 1
if j >= 0:
s += ord(num2[j]) - 48
j -= 1
out.append(chr(48 + s % 10))
carry = s // 10
return "".join(reversed(out))class Solution {
public:
string addStrings(string num1, string num2) {
string sb;
int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += num1[i--] - '0';
if (j >= 0) sum += num2[j--] - '0';
sb.push_back((char) ('0' + sum % 10));
carry = sum / 10;
}
reverse(sb.begin(), sb.end());
return sb;
}
};function addStrings(num1, num2) {
const out = [];
let i = num1.length - 1, j = num2.length - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
let sum = carry;
if (i >= 0) sum += num1.charCodeAt(i--) - 48;
if (j >= 0) sum += num2.charCodeAt(j--) - 48;
out.push(sum % 10);
carry = Math.floor(sum / 10);
}
return out.reverse().join("");
}Edge cases to test
- A final carry that creates an extra digit, like 999 + 1
- Strings of very different lengths
- One or both numbers equal to zero
Hints
Hint 1
Do it the way you add on paper: start from the last digit of each string.
Hint 2
Keep a carry. Each column is digit1 + digit2 + carry; write the last digit and carry the tens.
Hint 3
When one string runs out, treat its missing digits as 0, and do not forget a carry left after the loop.
FAQ
What is the best time complexity for Add Strings?
Optimal (two pointers from the right) runs in O(max(n, m)) time and O(max(n, m)) extra space. Each column is handled once and appending is amortized O(1); the final reverse is linear.
Which pattern does Add Strings use?
It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.
Is there a brute force solution for Add Strings?
Yes. Pad and add takes O(n²) time and O(n) space. Pad the shorter string with leading zeros so both have the same length, then add column by column from the right, prepending each digit to the result.
Which edge cases should I test for Add Strings?
A final carry that creates an extra digit, like 999 + 1; Strings of very different lengths; One or both numbers equal to zero.