Leetcode: 67. Add Binary

# Solution

**Primary idea**: Math: use carry and iterate from last to start**Time Complexity**: O(n), as we need to iterate through the whole string a and b**Space Complexity**: O(n), as Swift does not have a way to access a character in a string with O(1)

```
func addBinary(_ a: String, _ b: String) -> String {
// Note: Swift does not have a way to access a character in a string with O(1),
// thus we have to first transfer the string to a character array
let a = Array(a), b = Array(b)
var result = ""
var carry = 0
// Get last index of both string to go backward for calculation
var i = a.count - 1, j = b.count - 1
// Going backward and calculate the sum and carry digit by digit
while i>=0 || j>=0 || carry > 0 {
// Initialise the sum for the current position with the value of carry
var sum = carry
// If there is number from a, add it to sum
if i>=0 {
sum += Int(String(a[i]))!
i -= 1
}
// If there is number from b, add it to sum
if j>=0 {
sum += Int(String(b[j]))!
j -= 1
}
// Insert the calculated modulo into the beginning of result
result = "\(sum % 2)" + result
// Calculate the carry for the next calculation.
carry = sum/2
}
return result
}
addBinary("11", "1") // 100
addBinary("1010", "1011") // 10101
```