CF 102697046 - Binary Math

CF 102697046 - Binary Math

Rating: -
Tags: -
Solve time: 48s
Verified: yes

Solution

Problem Understanding

The task is to add two non-negative integers whose representations are given as binary strings. The first line contains one binary number, the second line contains another binary number, and the required output is their sum, also written in binary. The strings can have different lengths, so the addition has to handle missing higher-order digits as zeros.

For example, the input

101
11

represents (5) and (3). Their sum is (8), whose binary representation is 1000.

The statement does not specify a numeric upper bound for the lengths of the two strings. Since the numbers are represented directly as strings, the intended approach should work even when the binary values themselves are far too large for a fixed-width integer type. A solution that stores the numbers in a machine integer would unnecessarily impose a size restriction that the input does not impose. A linear-time solution is the natural target because every input digit may affect the carry propagation and must potentially be inspected.

There are a few edge cases that a careless implementation can mishandle. First, the numbers can have different lengths. For example,

1
111

has output

1000

because the missing digits of the first number are treated as zero. An implementation that only processes positions while both strings still have digits would stop too early and lose the leading carry.

A second edge case is a final carry. For

1
1

the correct output is

10

After processing the only pair of input digits, the carry is still one, so it must become a new most significant digit. An implementation that prints only the processed positions would incorrectly produce 0.

Leading zeroes are another possible source of trouble if the input is treated as a normal decimal integer representation. For example,

00101
0011

represents (5+3=8), so the output should be

01000

if the operation is understood as preserving the width of the input representation, but the usual interpretation of "return the sum in binary" is the canonical representation, 1000. The safe implementation below performs binary addition directly and naturally produces the canonical form without relying on the input strings having equal lengths.

Approaches

A brute-force way to think about the task is to enumerate possible numerical values and search for the correct sum. If the longer input has (L) binary digits, the represented number can be as large as (2^L-1). A search that considers every possible value up to that magnitude can require (\Theta(2^L)) candidates, and even checking a candidate's binary representation costs up to (O(L)). In the worst case that gives (\Theta(L2^L)) work, which becomes infeasible after only a few dozen input bits. The brute-force approach is correct because eventually it considers the actual sum, but it ignores the fact that binary addition has a very small local state.

The key observation is that each binary column depends only on three values: the two input bits and the carry coming from the less significant column. For two bits (a) and (b) with incoming carry (c), the resulting digit is

[ (a+b+c)\bmod 2 ]

and the outgoing carry is

[ \left\lfloor\frac{a+b+c}{2}\right\rfloor. ]

There are only four possible pairs of input bits and two possible carry values, so no global search is needed. We can reproduce exactly the same process used for ordinary paper-and-pencil addition, starting at the least significant digit and moving left.

The brute-force works because it searches the entire space of possible results, but fails because that space grows exponentially with the number of bits. The observation that a binary addition column depends only on the current bits and one carry reduces the problem to a single pass over the input.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	(O(L2^L))	(O(L))	Too slow
Binary Addition	(O(L))	(O(L))	Accepted

Here (L=\max(|a|,|b|)).

Algorithm Walkthrough

1. Read the two binary strings and set two indices to their last positions. We start from the right because the least significant digits are the first digits whose sum is known without needing a carry from another column.
2. Set the initial carry to zero. There is no digit to the right of the least significant position, so no carry enters the first addition.
3. While either string still has an unprocessed digit or a carry remains, read the current digit from each string. If an index has moved before the beginning of its string, use zero instead. This aligns the two numbers by their least significant bits even when their lengths differ.
4. Compute total = a_digit + b_digit + carry. The output bit is total % 2, while the next carry is total // 2. Since total can only be 0, 1, 2, or 3, the carry is always either zero or one.
5. Append the produced bit to a result list. The digits are generated from least significant to most significant, so the list is currently reversed relative to the normal representation.
6. Move both indices one position to the left and continue until no input digit and no carry remain.
7. Reverse the result and print it. The reversal restores the usual most-significant-bit-first representation.

Why it works

After processing any position, the carry stored by the algorithm is exactly the carry that ordinary binary addition would send into the next position. For the current position, the algorithm uses both actual input bits when they exist, zero for a missing bit, and precisely that incoming carry. The computed remainder modulo two is consequently the only valid output bit for the position, and integer division by two gives the only valid outgoing carry. By induction from the least significant position to the most significant one, every produced digit is correct. When all input digits have been consumed, processing continues if a carry remains, so a final leading 1 can never be lost.

Python Solution

import sys
input = sys.stdin.readline

def add_binary(a: str, b: str) -> str:
    i = len(a) - 1
    j = len(b) - 1
    carry = 0
    result = []

    while i >= 0 or j >= 0 or carry:
        x = ord(a[i]) - ord('0') if i >= 0 else 0
        y = ord(b[j]) - ord('0') if j >= 0 else 0

        total = x + y + carry
        result.append(str(total & 1))
        carry = total >> 1

        i -= 1
        j -= 1

    return ''.join(reversed(result))

def main():
    a = input().strip()
    b = input().strip()
    print(add_binary(a, b))

if __name__ == "__main__":
    main()

The two indices start at the last character of each string, which corresponds to the (2^0) position. Each iteration consumes exactly one column from the right.

The conditional expressions for x and y are what allow unequal-length strings to be added. Once an index becomes negative, the corresponding number contributes zero to every remaining column.

The bit calculation uses total & 1, which is equivalent to total % 2, and total >> 1, which is equivalent to integer division by two for these non-negative values. Both expressions directly reflect the binary arithmetic being performed.

The result is stored as characters rather than converting either input into a Python integer. This avoids dependence on the size of the numeric values and keeps the algorithm proportional to the number of input bits.

There is no integer-overflow issue because the algorithm never stores either potentially huge binary number as a machine-sized integer. The only numeric variables are the individual bits, the carry, and their sum.

Worked Examples

For the first example, the input is 101 and 11.

Position from right	First bit	Second bit	Carry in	Total	Output bit	Carry out
0	1	1	0	2	0	1
1	0	1	1	2	0	1
2	1	0	1	2	0	1
3	0	0	1	1	1	0

The generated bits are 0001 from right to left. Reversing them gives 1000, which is the binary representation of (5+3=8). The last row demonstrates why the loop must continue after both input strings have been exhausted: the remaining carry forms the new leading digit.

For a second example, consider

1111
1

Position from right	First bit	Second bit	Carry in	Total	Output bit	Carry out
0	1	1	0	2	0	1
1	1	0	1	2	0	1
2	1	0	1	2	0	1
3	1	0	1	2	0	1
4	0	0	1	1	1	0

The result is 10000. This trace exercises the case where a carry propagates through every remaining digit of the longer number. Treating missing digits as zero makes the fifth column work exactly like every other column.

Complexity Analysis

Measure	Complexity	Explanation
Time	(O(L))	Each input digit is processed once, where (L=\max(
Space	(O(L))	The output contains at most (L+1) bits, and the result list stores those bits before reversal.

The linear complexity is optimal up to constant factors because the algorithm must at least read the input digits. Even if the strings are extremely long, the amount of work grows only proportionally with their length, while the brute-force search grows exponentially.

Test Cases

import sys
import io

def add_binary(a: str, b: str) -> str:
    i = len(a) - 1
    j = len(b) - 1
    carry = 0
    result = []

    while i >= 0 or j >= 0 or carry:
        x = ord(a[i]) - ord('0') if i >= 0 else 0
        y = ord(b[j]) - ord('0') if j >= 0 else 0

        total = x + y + carry
        result.append(str(total & 1))
        carry = total >> 1

        i -= 1
        j -= 1

    return ''.join(reversed(result))

def solve():
    a = input().strip()
    b = input().strip()
    return add_binary(a, b)

def run(inp: str) -> str:
    global input
    old_stdin = sys.stdin
    old_input = input

    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    try:
        return solve() + "\n"
    finally:
        sys.stdin = old_stdin
        input = old_input

# Provided sample
assert run("101\n11\n") == "1000\n", "sample 1"

# Minimum-size inputs
assert run("0\n0\n") == "0\n", "minimum values"

# Final carry
assert run("1\n1\n") == "10\n", "final carry"

# Unequal lengths
assert run("1\n111\n") == "1000\n", "different lengths"

# All equal digits
assert run("111111\n111111\n") == "1111110\n", "all ones"

# Leading zeroes
assert run("00101\n0011\n") == "1000\n", "leading zeroes"

# Large input, exercising linear processing
n = 10000
assert run("1" * n + "\n" + "1\n") == "1" + "0" * (n - 1) + "0\n", "large input"

Test input	Expected output	What it validates
0 and 0	0	Minimum-size input and zero handling
1 and 1	10	A final carry must be emitted
1 and 111	1000	Different input lengths
111111 and 111111	1111110	Carry propagation through every column
00101 and 0011	1000	Leading zeroes do not affect the numerical sum
Two strings of 10000 and 1 bits	1 followed by 10000 zeroes	Linear behavior on a large input

The large test deliberately creates a carry at the least significant position and then leaves the rest of the longer number unchanged. It checks that the implementation does not accidentally stop after the shorter input is exhausted.

Edge Cases

For unequal lengths, consider the exact input

1
111

The first iteration adds (1+1), producing zero with carry one. The second iteration uses zero for the missing first-number digit and adds (0+1+1=2), again producing zero with carry one. The third iteration behaves identically, and the remaining carry produces the leading one. The final result is 1000. The explicit zero substitution for exhausted strings is what makes this work without special cases.

For a final carry, consider

1
1

The only input column gives (1+1=2), so the output bit is zero and the carry becomes one. Both input indices are now exhausted, but the loop condition still sees the nonzero carry. One more iteration outputs one, giving 10. Without or carry in the loop condition, the implementation would incorrectly return 0.

For long carry propagation, consider

1111
1

The least significant column produces zero and a carry. Every following column adds that carry to a 1, producing another zero and another carry. After the fourth input digit, the carry is still one, so a fifth iteration produces the leading one. The result is 10000. This is the case most likely to expose an implementation that mishandles the transition from the input digits to the final carry.

For leading zeroes, consider

00101
0011

The algorithm processes the strings exactly as written. The leading zeroes eventually contribute columns containing zero digits, while the significant suffix represents (5+3). The generated result is 1000, which is the canonical binary representation of the sum. No conversion to a fixed-width integer or trimming logic is required.