Матч
338, Бинарное увеличение (BinaryIncrementation)
Дивизион 2,
Уровень 1
Имеется строка, в которой
записано двоичное представление натурального числа n. Необходимо получить строку, содержащую двоичное представление
числа n + 1.
Класс: BinaryIncrementation
Метод: string plusOne(string x)
Ограничения: строка x
содержит от 1 до 30 символов ‘0’ и ‘1’, первый символ строки x равен ‘1’.
Вход. Строка, содержащая двоичное
представление натурального числа n.
Выход. Строка, содержащая двоичное представление числа n + 1.
Пример входа
|
x |
|
“10011” |
|
“1111” |
|
“1” |
Пример выхода
“10100”
“10000”
“10”
РЕШЕНИЕ
обработка строк
Проходим по строке с конца в
начало. Каждую единицу заменяем на ноль. Если встретился ноль – заменяем его на
единицу и заканчиваем обработку строки. Если исходная строка состоит из одних
единиц, то ответом будет строка, содержащая единицу и столько нулей, сколько
единиц в исходной строке.
ПРОГРАММА
#include <cstdio>
#include <string>
using namespace std;
class BinaryIncrementation
{
public:
string plusOne(string x)
{
int i;
for(i = x.size() - 1; i >= 0; i--)
{
if (x[i] == '0')
break;
x[i] = '0';
}
if (i >= 0) x[i] = '1'; else
x = string(1,'1') + x;
return x;
}
};