62. Binary Adder
A tiny calculator stores numbers as strings of digits. You are given two non-negative whole numbers a and b, written in binary (only the characters 0 and 1).
Return their sum, also written as a string in binary (only the characters 0 and 1). Neither input has leading zeros unless it is exactly "0", and the answer must follow the same rule. The numbers can be far longer than any built-in integer type, so add them digit by digit from the right while carrying.
Example 1
- Input:
- a = "110", b = "101"
- Output:
- "1011"
- Explanation:
6 + 5 = 11, which is 1011 in binary.
Example 2
- Input:
- a = "1", b = "111"
- Output:
- "1000"
- Explanation:
1 + 7 = 8, which is 1000 in binary; the carry travels through every digit.
Constraints
1 ≤ a.length, b.length ≤ 104
a and b contain only 0 and 1
No leading zeros except for the number 0 itself
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(max(n, m))
- Space
- O(max(n, m))