-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathadd_binary.py
More file actions
42 lines (33 loc) · 1.07 KB
/
add_binary.py
File metadata and controls
42 lines (33 loc) · 1.07 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
"""
Add Binary
Given two binary strings, return their sum as a binary string.
Reference: https://leetcode.com/problems/add-binary/
Complexity:
Time: O(max(m, n)) where m, n are lengths of the two strings
Space: O(max(m, n))
"""
from __future__ import annotations
def add_binary(first: str, second: str) -> str:
"""Add two binary strings and return their binary sum.
Args:
first: A string representing a binary number.
second: A string representing a binary number.
Returns:
A string representing the binary sum of the two inputs.
Examples:
>>> add_binary("11", "1")
'100'
"""
result = ""
carry, index_a, index_b = 0, len(first) - 1, len(second) - 1
zero = ord("0")
while index_a >= 0 or index_b >= 0 or carry == 1:
if index_a >= 0:
carry += ord(first[index_a]) - zero
index_a -= 1
if index_b >= 0:
carry += ord(second[index_b]) - zero
index_b -= 1
result = chr(carry % 2 + zero) + result
carry //= 2
return result