Binary Addition of Strings | Dataford Interview Questions

Oscar Health's member eligibility workflow may represent compact flags or counters as binary strings. Implement binary addition for two non-negative binary strings without converting either input to a built-in integer type.

Return the binary representation of their sum without leading zeros, except that the result for zero must be "0".

Formal Specification

Implement add_binary(a, b):

Input: two strings a and b, each containing only the characters 0 and 1.
Output: a string containing only 0 and 1, representing the exact sum of the two inputs in base two.
Do not use integer parsing, arbitrary-precision conversion, or floating-point arithmetic to convert the complete input strings.

Process digits from right to left, maintaining a carry just as in decimal addition. The inputs may have different lengths and may contain leading zeros.

Constraints

1 <= len(a), len(b) <= 10^5
Each input contains only the characters 0 and 1.
Inputs may contain leading zeros.
The result must not contain leading zeros unless it is exactly "0".

Function Signature

def add_binary(a, b):

Your question is Binary Addition of Strings. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem