Given two binary strings, write a function that adds them. You are not allowed to use any built in string to int conversions or parsing tools. E.g. Given "100" and "111" you should return "1011". What is the time and space complexity of your algorithm?

Question

Anonymous · Accepted Answer

In Python:

def normalize_length(str1, str2):
    len1 = len(str1)
    len2 = len(str2)
    if (len1 = 0):
        if (input2[i] == "1") and (input1[i] == "1"):
            if(carry):
                result = "1" + result
                carry = 1
            else:
                carry = 1
                result = "0" + result
            i -= 1
        if (input2[i] == "1") and (input1[i] == "0"):
            if (carry):
                result = "0" + result
            else:
                result = "1" + result
            i -= 1
        if (input2[i] == "0") and (input1[i] == "1"):
            if (carry):
                result = "0" + result
            else:
                result = "1" + result
            i -=1
        if (input2[i] == "0") and (input1[i] == "0"):
            if (carry):
                result = "1" + result
                carry = 0
            else:
                result = "0" + result
            i -=1
    if(carry):
        result = "1" + result
        carry = 0
    return(result)

str1 = "111"
str2 = "1011"
print(normalize_length(str1, str2))
print(add_binary(str1, str2))


Obviously there are better ways to do this, but hey: my solution is O(N).

Anonymous · Answer

Ignore the answer above - didn't realize that Glassdoor would cut off parts of my answer for being too long. Assuming you already wrote the normalizing code to make the input lengths the same by adding zeros:

def add_binary(input1, input2):
    normalized = normalize_length(input1, input2)
    input1 = normalized[0]
    input2 = normalized[1]
    length = len(input1)
    result = ""
    
    carry = 0
    i = length-1
    while(i >= 0):
        if (input2[i] == "1") and (input1[i] == "1"):
            if(carry):
                result = "1" + result
                carry = 1
            else:
                carry = 1
                result = "0" + result
            i -= 1
        if (input2[i] == "1") and (input1[i] == "0"):
            if (carry):
                result = "0" + result
            else:
                result = "1" + result
            i -= 1
        if (input2[i] == "0") and (input1[i] == "1"):
            if (carry):
                result = "0" + result
            else:
                result = "1" + result
            i -=1
        if (input2[i] == "0") and (input1[i] == "0"):
            if (carry):
                result = "1" + result
                carry = 0
            else:
                result = "0" + result
            i -=1
    if(carry):
        result = "1" + result
        carry = 0
    return(result)

prep · Answer

def calc_bin_sum(bin1, bin2):
	## bin1 conversion to a number based in 10
	b1 = 0
	for i in range(len(bin1)):
		b1 = b1 + int(bin1[i]) * (2**i)

	## bin2 conversion to a number based in 10
	b2 = 0
	for j in range(len(bin2)):
		b2 = b2 + int(bin2[j]) * (2**i)

	## Add two numbers
	corr_based_10 = b1 + b2

	## Change it back to binary
	def trans(x):
		binary = []
		while x:
			binary.append(x % 2)
			x >>= 1
		return binary
	return ''.join(map(str, trans(corr_based_10)))

vish · Answer

A good perl programmer can write perl in any language
reduce(
        lambda st_car, nxt : (st_car[0] + str((st_car[1] + nxt) % 2),
                                                     int((st_car[1] + nxt)/2)),
        map(lambda a:sum(map(int, a)),
                   zip_longest(reversed('11'),reversed('101010'), fillvalue='0')),
                   ('', 0)
  )[0]

MKS · Answer

Using Python, 

def binaryAdd(str1, str2):
    len_str1 = len(str1)
    len_str2 = len(str2)
    if len_str1 > len_str2:
        max_len = len_str1
        min_len = len_str2
        max_str = str1
        min_str = str2
    else:
        max_len = len_str2
        min_len = len_str1
        max_str = str2
        min_str = str1
    # resulting str
    res = ''
    carry_over = 0  # 0 or 1 at all times
    for i in range(min_len-1,-1,-1):
        temp_sum = int(min_str[i]) + int(max_str[i+(max_len-min_len)]) + carry_over
        res = str(temp_sum % 2) + res  # modulo 2; remainder is the digit
        carry_over = int(temp_sum/2)
    for i in range(max_len-min_len-1,-1,-1):
        temp_sum = int(max_str[i]) + carry_over
        res = str(temp_sum % 2) + res
        carry_over = int(temp_sum/2)
    if carry_over == 1:
        res = '1' + res

    print(res)

Max · Answer

Here's how I would've done it:

def add_bin(str1, str2):
    len1 = len(str1)
    len2 = len(str2)
    diff = len2 - len1

    #padded zeros
    if diff  0:
        for zero in range(diff):
            str1 = '0'+str1
    results = []
    carry = 0

    #binary algebra
    for bit1,bit2 in zip(reversed(str1), reversed(str2)):
        if bit1 == '1' and bit2 == '1':
            if carry == 1:
                results.append('1')
                carry = 1
            else:
                results.append('0')
                carry = 1
        elif (bit1 == '0' and bit2 == '1') or (bit1 == '1' and bit2 == '0'):
            # print('hi')
            if carry == 1:
                results.append('0')
                carry = 1
            else:
                results.append('1')
                carry = 0

        elif (bit1 == '0' and bit2 == '0'):
            if carry == 1:
                results.append('1')
                carry = 0
            else:
                results.append('0')
                carry = 0

    #last carry:
    if carry == 1:
        results.append('1')
        
    return ''.join(reversed(results))

str1 = "100"
str2 = "111"
print(add_bin(str1, str2))

Meta

Meta interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?