Задача: сложить двоичные числа, представленные в виде строк
2026-02-21 07:32 Diff
https://skillbox.ru/media/code/zadacha-slozhit-dvoichnye-chisla-predstavlennye-v-vide-strok/

#статьи

  • 12 окт 2022
  • 0

Задача: сложить двоичные числа, представленные в виде строк

Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня складываем двоичные числа.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Даны два двоичных числа в виде строк a и b. Нужно вернуть их суммы в виде строки.

Ввод: a = "11", b = "1" Вывод: "100" Ввод: a = "1010", b = "1011" Вывод: "10101"

Решение

Чтобы решить эту задачу, мы должны начать с конца и посимвольно складывать цифры. Создадим два указателя — для каждой из строк. На старте они будут ссылаться на последние символы строк. Теперь просто пойдём с конца строк к началу, уменьшая значения указателей на один.

Главная проблема здесь — не забыть о числах, которые переносятся в следующий разряд. А ещё нужно помнить, что одна строка может быть длиннее другой. В этом случае придётся добавить оставшиеся символы из более длинной строки к результату.

Чтобы работать со строками было удобно, я использовал StringBuilder. В Java это самый эффективный способ для операций на изменение строк.

Вот как алгоритм будет реализован на Java:

public String addBinary(String aa, String bb) { char[] aChars = aa.toCharArray(); char[] bChars = bb.toCharArray(); int rest = 0; int readerA = aChars.length - 1; int readerB = bChars.length - 1; StringBuilder sb = new StringBuilder(); while (readerA >= 0 && readerB >= 0){ int a = aChars[readerA] - '0'; int b = bChars[readerB] - '0'; int sum = a + b + rest; rest = sum/2; sb.append(sum % 2); readerA--; readerB--; } while(readerA >= 0){ int a = aChars[readerA] - '0'; int sum = a + rest; rest = sum/2; sb.append(sum % 2); readerA--; } while(readerB >= 0){ int b = bChars[readerB] - '0'; int sum = b + rest; rest = sum/2; sb.append(sum % 2); readerB--; } if (rest != 0){ sb.append(rest); } return sb.reverse().toString(); }

Результаты

Временная сложность: O(n) — так как мы перебирали все символы в строках.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество памяти (максимальный размер памяти — две строки).

Научитесь: Профессия Java-разработчик + ИИ Узнать больше