Two counters report their values as strings of binary digits ('0' and '1'), most significant digit first. The values can be far too long for any built-in integer type in C++ or Java.
Write add_binary(a: str, b: str) -> str that returns their sum as a binary string, also most significant digit first, with no leading zeros (the sum zero is written "0").
add_binary("1011", "111") # "10010" (11 + 7 = 18)
add_binary("1", "1") # "10"
add_binary("0", "0") # "0"
add_binary("100", "0") # "100"
Constraints:
1 <= len(a), len(b) <= 5 * 10^5.- Each string is
"0"or starts with'1'.
Work digit by digit rather than converting whole strings into numbers. Aim for O(len(a) + len(b)). Building the answer by adding a character to the front of a string each step copies the whole string every time, so it is quadratic.
Show hint
do it the way you would on paper: start from the rightmost digits, keep a carry of 0 or 1, and emit one result digit per column. Collect the digits in reverse and flip them once at the end.