leetcode day 16: add two binary strings

You are given two strings, possibly of different lengths, and you are to add them as if they were binary numbers, returning the result as a string.

My first cut was to use an iterator function to scan over the strings, delivering the digits in the order I want them, then summing them via a switch statement. Getting the carry right was the only real issue.

func addBinary(a string, b string) string {
    if a == "0" {
        return b
    } else if b == "0" {
        return a
    } else {
        iterA := nextDigit(a)
        iterB := nextDigit(b)
        max := len(b)
        if len(a) > max {
            max = len(a)
        }
        carry := 0
        sum := ""
        for i:=0; i < max; i ++ {
            x := iterA()
            y := iterB()
            switch x+y+carry {
                case 0:
                sum = "0" + sum
                case 1:
                sum = "1" + sum
                carry = 0
                case 2:
                sum = "0" + sum
                carry = 1
                case 3:
                sum = "1" + sum
                carry = 1
            }
        }
        if carry != 0 {
            sum = "1" + sum
        }
        return sum
    }
}

func nextDigit(s string) func() int {
    digits := []byte(s)
    i := len(digits)-1
    var one byte = '1'
    return func() int {
        if i >= 0 {
            j := digits[i]
            fmt.Println(j)
            i--
            if j == one {
                return 1
            } else {
                return 0
            }
        } else {
            return 0
        }
    }
}

This is quite slow: 5th percentile in speed, 19th percentile in memory. Let’s look at speed hacks. The call to the closure for every digit is probably hurting both of those, so let’s inline the logic and Cheaty McCheatface the values so we’re working with ints as much as possible:

unc addBinary(a string, b string) string {
    if a == "0" {
        return b
    } else if b == "0" {
        return a
    } else {
        ascan := len(a) - 1
        bscan := len(b) - 1
        carry := 0
        sum := ""
        for ascan >= 0  || bscan >=  0 {
            var aVal, bVal int
            if ascan < 0 {
                aVal = 48
            } else {
                aVal = int(a[ascan])
                ascan--
            }
            if bscan < 0 {
                bVal = 48
            } else {
                bVal = int(b[bscan])
                bscan--
            }
            switch aVal+bVal+carry {
                case 48+48+0:
                sum = "0" + sum
                case 48+49+0:
               sum = "1" + sum
                carry = 0
                case 49+49+0:
                sum = "0" + sum
                carry = 1
                case 49+49+1:
                sum = "1" + sum
                carry = 1
            }
        }
        if carry != 0 {
            sum = "1" + sum
        }
        return sum
    }
}

func nextDigit(s string) func() int {
    digits := []byte(s)
    i := len(digits)-1
    var one byte = '1'
    return func() int {
        if i >= 0 {
            j := digits[i]
            fmt.Println(j)
            i--
            if j == one {
                return 1
            } else {
                return 0
            }
        } else {
            return 0
        }
    }
}

Better. 100% on speed, but 18% on memory, no doubt all those string allocations. Let’s append and then reverse the output instead.

func addBinary(a string, b string) string {
    if a == "0" {
        return b
    } else if b == "0" {
        return a
    } else {
        ascan := len(a) - 1
        bscan := len(b) - 1
        max := ascan
        if bscan > ascan {
            max = bscan
        }
        // ensure we only allocate once
        byteString := make([]byte, max+2)
        optr := max+1
        carry := 0

        for ascan >= 0  || bscan >=  0 {
            var aVal, bVal int
            if ascan < 0 {
                aVal = 48
            } else {
                aVal = int(a[ascan])
                ascan--
            }
            if bscan < 0 {
                bVal = 48
            } else {
                bVal = int(b[bscan])
                bscan--
            }
            switch aVal+bVal+carry {
                case 48+48+0:
                //sum = "0" + sum
                byteString[optr] = 48
                optr--
                case 48+49+0:
                //sum = "1" + sum
                byteString[optr] = 49
                optr--
                carry = 0
                case 49+49+0:
                //sum = "0" + sum
                byteString[optr] = 48
                optr--
                carry = 1
                case 49+49+1:
                //sum = "1" + sum
                byteString[optr] = 49
                optr--
                carry = 1
            }
        }
        if carry != 0 {
            byteString[optr] = 49
        } else {
            optr++
        }

        sum := string(byteString[optr:])
        return sum
    }
}

Significantly harder to get right (remembering to fix all of the magic numbers is a particular pain) but now memory usage is at the 78th percentile, which is a huge boost. I’d call that a winner, modulo the dependencies we’ve added to make the memory usage smaller.