Дано целое число N. Какое наименьшее целое число больше, чем N, которое имеет только 0 или 1 в качестве цифр?

У меня есть целое число N. Я должен найти наименьшее целое число больше N, которое не содержит цифр, кроме 0 или 1. Например: если N = 12тогда ответ - 100. Я кодировал подход грубой силы в C ++.

int main() {
    long long n;
    cin >> n;

    for (long long i = n + 1; ; i++) {
        long long temp = i;
        bool ok = true;
        while (temp != 0) {
            if ( (temp % 10) != 0 && (temp % 10) != 1) {
                ok = false;
                break;
            }
            temp /= 10;
        }
        if (ok == true) {
            cout << i << endl;
            break;
        }
    }
}

Проблема в том, что мой подход слишком медленный. Я считаю, что есть очень эффективный подход для решения этой проблемы. Как я могу решить эту проблему эффективно?

1. Инкремент N,

2. Начиная слева, сканируйте, пока не найдете цифру выше 1. Увеличьте частичное число перед ним и обнулите остальные.

Например

12 -> 13 -> 1|3 -> 10|0
101 -> 102 -> 10|2 -> 11|0
109 -> 110 -> 110|
111 -> 112 -> 11|2 -> 100|0
198 -> 199 -> 1|99 -> 10|00
1098 -> 1099 -> 10|99 -> 11|00
10203 -> 10204 -> 10|204 -> 11|000
111234 -> 111235 -> 111|235 -> 1000|000
...

Доказательство:

Запрашиваемое число должно быть не менее N + 1, поэтому мы увеличиваем его. Сейчас мы ищем число больше или равно.

Давайте назовем префикс начальными цифрами 0/1 и суффикс после. Мы должны заменить первую цифру суффикса на ноль и установить больший префикс. Наименьший подходящий префикс - это текущий префикс плюс один. И самый маленький подходящий суффикс - это все нули.

Обновить:

Я забыл указать, что префикс должен увеличиваться как двоичное число , иначе могут появиться запрещенные цифры.

Другая возможность будет следующей:

• Вы начинаете с наибольшего десятичного числа типа "1111111 ... 1111", поддерживаемого используемым типом данных

  Алгоритм предполагает, что входное значение меньше этого числа; в противном случае вам придется использовать другой тип данных.

  Пример: при использовании long longвы начинаете с номера 1111111111111111111.

• Затем обработайте каждую десятичную цифру слева направо:
  • Попробуйте изменить цифру от 1 до 0.
  • Если результат все еще больше, чем ваш ввод, сделайте изменение (измените цифру на 0).
  • В противном случае цифра остается 1.

пример

Input = 10103
Start:  111111
Step 1: [1]11111, try [0]11111; 011111 > 10103 => 011111 
Step 2: 0[1]1111, try 0[0]1111; 001111 < 10103 => 011111
Step 3: 01[1]111, try 01[0]111; 010111 > 10103 => 010111
Step 4: 010[1]11, try 010[0]11; 010011 < 10103 => 010111
Step 5: 0101[1]1, try 0101[0]1; 010101 < 10103 => 010111
Step 6: 01011[1], try 01011[0]; 010110 > 10103 => 010110
Result: 010110

Доказательство правильности:

В этом алгоритме мы обрабатываем цифру за цифрой. На каждом шаге есть цифры, значение которых уже известно, и цифры, значения которых еще не известны.

На каждом шаге мы проверяем крайнюю левую неизвестную цифру.

Мы устанавливаем эту цифру на «0», а все остальные неизвестные цифры на «1». Поскольку исследуемая цифра является самой значимой из неизвестных цифр, результирующее число представляет собой наибольшее возможное число, причем эта цифра равна «0». Если это число меньше или равно входному значению, измеряемая цифра должна быть «1».

С другой стороны, результирующее число меньше всех возможных чисел, где исследуемая цифра равна «1». Если результирующее число больше, чем ввод, цифра должна быть «0».

Это означает, что мы можем вычислить одну цифру на каждом шаге.

Код C

(Код C должен работать и на C ++):

long long input;
long long result;
long long digit;

... read in input ...

result = 1111111111111111111ll;
digit = 1000000000000000000ll;

while( digit > 0 )
{
    if(result - digit > input)
    {
        result -= digit;
    }
    digit /= 10;
}

... print out output ...

Позвольте мне предложить пару альтернатив.

I. Увеличение. Считайте это модификацией метода @YvesDaoust.

1. Увеличить N на 1
2. Развернуть результат с ведущим нулем
3. Переходите от последней ко второй цифре
   (a), если она меньше 2, затем оставьте все как есть
   (b) в противном случае установите его на 0 и увеличьте предыдущий
4. Повторите шаги 3а, б

Примеры:

1. N = 0 -> 1 -> (0)|(1) -> 1
2. N = 1 -> 2 -> (0)|(2) -> (1)|(0) -> 10
3. N = 101 -> 102 -> (0)|(1)(0)(2) -> (0)|(1)(1)(0) -> (0)|(1)(1)(0) -> (0)|(1)(1)(0) -> 110
4. N = 298 -> 299 -> (0)|(2)(9)(9) -> (0)|(2)(10)(0) -> (0)|(3)(0)(0) -> (1)|(0)(0)(0) -> 1000

Вы получите результат в десятичном формате.

II. Разделив.

1. Увеличить N на 1
2. Установите сумму 0
3. Разделите результат на 10, чтобы получить части div (D) и mod (M)
4. Проверьте M
   (a), если M превышает 1, затем увеличьте D
   (b), в противном случае увеличьте сумму на M * 10 ^k , где k - текущий номер итерации (начиная с 0)
5. Повторите шаги 3,4, пока D не станет 0

Пример 1:

1. N = 0 -> N = 1
2. sum = 0
3. 1/10 -> D == 0, M == 1 -> sum = sum + 1*10^0 == 1
4. D == 0 -> sum == 1

Пример 2:

1. N = 1 -> N = 2
2. sum = 0
3. 2/10 -> D == 0, M == 2 -> D = D + 1 == 1
4. 1/10 -> D == 0, M == 1 -> sum = sum + 1*10^1 == 10
5. D == 0, sum == 10

Пример 3:

1. N = 101 -> N = 102
2. sum = 0
3. 102/10 -> D == 10, M == 2 -> D = D + 1 == 11
4. 11/10 -> D == 1, M == 1 -> sum = sum + 1*10^1 = 10
5. 1/10 -> D == 0, M == 1 -> sum = sum + 1*10^2 == 10 + 100 == 110
6. D == 0, sum == 110

Пример 4:

1. N = 298 -> N = 299
2. sum = 0
3. 299/10 -> D == 29, M == 9 -> D = D + 1 == 30
4. 30/10 -> D == 3, M == 0 -> sum = sum + 0*10^1 == 0
5. 3/10 -> D == 0, M == 3 -> D = D + 1
6. 1/10 -> D == 0, M == 1 -> sum = sum + 1*10^3 == 1000
7. D == 0, sum == 1000