Understanding the Problem

It is to add two binaries in string format. For instance, if a=”1” and b=”11” the returned value should be ”100” in a string format as well as the input format.

Approach

There were two approaches. One was to utilise the internal Python function int() and bin() to change the binary to decimal to deal with the sum-up process and again change the decimal to binary.

The other one is to go through numbers backwards then calculate binaries. I tried both.

Solution

• With the internal function

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        summed_num = int(a, 2) + int(b, 2)

        binary = bin(summed_num)
        return binary.split("b")[1]

The code is extremely simple. int(a, 2) and int(b, 2) will take a and b as binary then change it to decimal to sum. bin(summed_num) will turn the summed number into the binary. If there are values as a=”1” and b=”11”, the summed value of a and b will be 4, which will then be “0b100”. This is in string type. 0b is a prefix to indicate this is in a binary format. As we do not need this, split the string by “b” then take only the number on the right side.

• Without the internal function

But this time I wanted to solve the problem without utilising the internal funtions like int() or bin(). Steps to solve the problem are as follows.

1. Determine which string has a longer length. It is to take iteration twice in turns

2. Go through the first for loop with the shorter string’s length so to prevent the index out of range error I was calculating from the end with [-(idx)] index one by one, with surplus value so to determine whether to give 1 to the next digit or not

3. Add the calculated number to the binary list. I did binary = [str(summed)] + binary to add the summed value to the beginning of the list

4. If the lengths of a and b are different, take another loop to make sure the surplus is added to the rest of the digits

5. Finally add 1 as the first digit if there is surplus

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        longer = a if len(a) >= len(b) else b
        shorter = a if len(a) < len(b) else b

        surplus = 0
        binary = []

        # calc from the shorter view
        for i in range(len(shorter)):
            idx = i + 1
            summed = int(longer[-(idx)]) + int(shorter[-(idx)]) + surplus # surplus from the previous
            if summed == 2:
                surplus = 1
                summed = 0
            elif summed == 3:
                surplus = 1
                summed = 1
            else:
                surplus = 0

            binary = [str(summed)] + binary

        # calc with the surplus
        if len(longer) > len(shorter):
            for i in range(len(shorter), len(longer)):
                idx = i + 1
                summed = int(longer[-(idx)]) + surplus
                if summed == 2:
                    surplus = 1
                    summed = 0
                elif summed == 3:
                    surplus = 1
                    summed = 1
                else:
                    surplus = 0
                binary = [str(summed)] + binary
                print(idx, binary, surplus, longer[-(idx)])


        if surplus:
            return "".join(["1"] + binary)
        return "".join(binary)

Reflection

The problem was not as difficult as it looks if we get to utilise the functions already provided for programmers, but it was another story to code everything from the bottom to build my own algorithm. The concept and how-to-solve was in my head already, yet to code what I thought of was a challenge and difficult in some ways as I needed to debug in each step to make sure the values are correct in the way I thing it should be.

It was somewhat fun though.