Тимофей спросил у Гоши, умеет ли тот работать с числами в двоичной системе счисления. Он ответил, что проходил это на одной из первых лекций по информатике. Тимофей предложил Гоше решить задачку. Два числа записаны в двоичной системе счисления. Нужно вывести их сумму, также в двоичной системе. Встроенную в язык программирования возможность сложения двоичных чисел применять нельзя.
Решение должно работать за O(N), где N –— количество разрядов максимального числа на входе.
Формат ввода
Два числа в двоичной системе счисления, каждое на отдельной строке. Длина каждого числа не превосходит 10 000 символов.
Формат вывода
Одно число в двоичной системе счисления.
ch1 = input()
ch2 = input()
if (len(ch1) >= len(ch2)):
n = len(ch1)
ch2 = ch2.zfill(n)
else:
n = len(ch2)
ch1 = ch1.zfill(n)
ch1 = list(ch1)
ch2 = list(ch2)
for i in range(len(ch1)):
ch1[i] = int(ch1[i])
for i in range(len(ch2)):
ch2[i] = int(ch2[i])
ch1.reverse()
ch2.reverse()
ch_it = []
if (len(ch1) >= len(ch2)):
n = len(ch1)
else:
n = len(ch1)
flag = 0
for i in range(n):
temp = ch1[i] + ch2[i] + flag
if temp == 0 :
ch_it.append(0)
elif temp == 1:
ch_it.append(1)
flag = 0
elif temp == 2:
ch_it.append(0)
flag = 1
else:
ch_it.append(1) # равно 3
flag = 1
if flag == 1:
ch_it.append(1)
ch_it.reverse()
#print(ch_it)
for i in range(len(ch_it)):
print(ch_it[i], end='')