Two counters report their values as binary strings, most significant digit first, often too long for any built-in integer type in C++ or Java.
Write add_binary(a: str, b: str) -> str: their sum as a binary string with no leading zeros (zero is "0").
add_binary("1011", "111") # "10010" (11 + 7 = 18)
add_binary("1", "1") # "10"
add_binary("0", "0") # "0"
add_binary("100", "0") # "100"
Each string has up to 5 * 10^5 digits and is "0" or starts with '1'. Work digit by digit rather than converting whole strings into numbers.
⭐ Bonus: a speed test with 500,000-digit strings earns a star in O(len(a) + len(b)). Adding a character to the front of a string each step copies it every time, which is quadratic.
Show hint
do it as on paper: from the right, keep a carry of 0 or 1, emit one digit per column, and reverse once at the end.