Problem

Given 2 strings s1 and s2 that contain binary numbers, we need to produce another string containing the sum of these numbers.

Examples:

Solution

fn add_binary_strings(s1: &str, s2: &str) -> String {
    let (long_str, short_str) = if s1.len() > s2.len() {
        (s1, s2)
    } else {
        (s2, s1)
    };

    let mut short_iter = short_str.chars().rev();
    let mut carry = 0;
    let mut res: String = long_str
        .chars()
        .rev()
        .map(|lchar| {
            let (char, car) = match (lchar, short_iter.next(), carry) {
                ('0', Some('0'), 0) => ('0', 0),
                ('0', Some('0'), 1) => ('1', 0),
                ('0', Some('1'), 0) => ('1', 0),
                ('0', Some('1'), 1) => ('0', 1),
                ('1', Some('0'), 0) => ('1', 0),
                ('1', Some('0'), 1) => ('0', 1),
                ('1', Some('1'), 0) => ('0', 1),
                ('1', Some('1'), 1) => ('1', 1),
                ('0', None, 0) => ('0', 0),
                ('1', None, 0) => ('1', 0),
                ('0', None, 1) => ('1', 0),
                ('1', None, 1) => ('0', 1),
                _ => panic!("incorrect input"),
            };
            carry = car;
            char
        })
        .collect();

    if carry == 1 {
        res.push('1');
    }

    res.chars().rev().collect()
}

Explanation

We iterate over the (reversed) longer input string long_str, also moving the iterator over the (reversed) shorter input string along the way (short_iter.next()). Also, we maintain the mutable variable carry that keeps a digit (could contain only 0 or 1 value) that is transferred from one column of digits to another column of more significant digits (see: Carry in Wikipedia).

And then on each iteration, we just need to process all possible cases, which Rust's pattern matching helps to make very visual.

For example, ('0', Some('0'), 0) => ('0', 0) means that we need to sum '0' and '0', and there is no carried 1 digit from the previous column. As a result, we produce '0' and also indicate that there is no 1 to carry to another column.

For example, ('1', Some('1'), 0) => ('0', 1) means that we need to sum '1' and '1', and there is no carried 1 digit from the previous column. As a result, we produce '0' and also indicate that there is 1 to carry to another column.

For example, ('0', None, 0) => ('0', 0) means that there is no digit (None) for the shorter string at this point already (in case the input strings have different lengths). As a result, we just return '0' from the longer string and also indicate that there is no 1 to carry to another column.

At the end of the function, we add the rightmost '1', in case we need to carry one more digit after completing the string traversal (carry == 1), and then reverse the resulting string to produce the final result.

Complexity

The time complexity of the solution is O(n) (where n is the maximum length of the input strings). The auxiliary space complexity is also O(n) to store the result string.

---

Rust Playground with this code