Leet_Code/0067_add_binary.py at master · Kcheung42/Leet_Code · GitHub

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#------------------------------------------------------------------------------
# Question: 0067_add_binary.py
#------------------------------------------------------------------------------
# tags: #Easy #String
'''
Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"
Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

'''

#------------------------------------------------------------------------------
# Solutions
#------------------------------------------------------------------------------
from typing import *

class Solution:
    '''
    Time: O(n)
    '''
    def addBinary(self, a: str, b: str) -> str:
        n = max(len(a), len(b))
        a , b = a.zfill(n), b.zfill(n)
        carry = 0
        res = ""
        for i in range(n-1, -1, -1):
            # cur_sum = int(a[i]) + int(b[i]) + carry
            # without using int
            cur_sum = (a[i] == '1') + (b[i] == '1') + carry
            carry, rem = divmod(cur_sum,2)
            res = str(rem) + res
        if carry:
            res = str(carry) + res
        return res


class Solution2:
    '''
    without using int
    '''
    def addBinary(self, a, b):
        res = ''
        carry = 0
        a_idx = len(a) - 1
        b_idx = len(b) - 1
        while a_idx >= 0 or b_idx >= 0 or carry:
            curval = (a_idx >= 0 and a[a_idx] == '1') + (b_idx >= 0 and b[b_idx] == '1')
            carry, rem = divmod(curval + carry, 2)
            res = str(rem) + res
            a_idx -= 1
            b_idx -= 1
        return res

#------------------------------------------------------------------------------
# Tests
#------------------------------------------------------------------------------
import unittest

class TestSolution(unittest.TestCase):
    def test_simple1(self):
        s = Solution()
        a = "1011"
        b = "1011"
        self.assertEqual(s.addBinary(a,b) , "10110")

    def test_simple2(self):
        s = Solution()
        a = "1011"
        b = "11111011"
        self.assertEqual(s.addBinary(a,b) , "100000110")

    def test_simple3(self):
        s = Solution()
        s2 = Solution2()
        a = "1010"
        b = "1011"
        self.assertEqual(s.addBinary(a,b) , "10101")
        self.assertEqual(s2.addBinary(a,b) , "10101")


unittest.main(verbosity=2)