iOS Interview - Leetcode 67. Add Binary

May 29, 2024 • 2 min read • #swift, #interview, #leetcode

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