Friedrich Ewald My Personal Website

Leetcode: Add binary

The task is to add two binary numbers of various length. There is more than one possible solution. First, the basic solution which doesn’t use too many builtin Python functions works as follows: Reverse the strings containing the numbers. Then Iterate in a loop as long as we didn’t reach the end of both strings. Write the current position to a temporary variable if it’s still in the boundaries of the string. Then add a potential overflow and handle it if the sum of a + b + overflow > 1. Finally, check for the overflow at the end and add a 1 and reverse the string again before returning it. This can be solved much simpler with builtin Python functions. First, the manual solution that can be transferred in any programming language. 

class Solution:
  def addBinary(self, a: str, b: str) -> str:
    # Reverse strings
    a = a[::-1]
    b = b[::-1]

    # Prepare output
    out = ''

    i = 0
    overflow = 0
    while i < len(a) or i < len(b):
      aa, bb = 0, 0
      if i < len(a):
        aa = a[i]
      if i < len(b):
        bb = b[i]

      s = int(aa) + int(bb) + overflow
      out += str(s%2)
      if s > 1:
        overflow = 1
      else:
        overflow = 0

      i += 1

    if overflow > 0:
      out += str(overflow)

    return out[::-1]
    


if __name__ == '__main__':
  s = Solution().addBinary
  print(s('11', '1'), '100')
  print(s('1010', '1011'), '10101')
  print(s('0', '0'), '0')
  print(s('0', '1'), '1')
  print(s('100', '0'), '100')
  print(s('100', '100'), '1000')
Runtime: 67 ms, faster than 19.66% of Python3 online submissions for Add Binary. Memory Usage: 13.9 MB, less than 25.21% of Python3 online submissions for Add Binary. Now the solution that uses builtin Python functions. 
class Solution:
  def addBinary(self, a: str, b: str) -> str:
    # Convert to integer using base 2
    a = int(a, base=2)
    b = int(b, base=2)

    # Convert back to binary and skip the `0b` prefix
    return bin(a+b)[2:]
The runtime of both approaches is about the same.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts