# Rust Interview Puzzles: Sum 2 binary strings

·

### Problem

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

#### Examples:

 Input `s1` Input `s2` Output `10000` `1` `10001` `1` `111` `1000` `111` `111` `1110` `1011` `1010` `10101`

### 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