Генерация числовой последовательности

Question

Учитывая целое число N (0 M больше N , M имеет одинаковую длину с N , а сумма цифр равна. если M не существует, вернуть -1

пример:

N = 134, M = 143, // 1 + 3 + 4 = 1 + 4 + 3

N = 020, M = 101, // 2 = 1 + 1, кажется, 0 можно добавить, чтобы сделать длину равной

N = 120, M = 201, // 2 = 1 + 1

Вопрос - это письменный тестовый вопрос, который я задал сегодня, я понятия не имею, как его решить в огромном объеме N .

Answer 1

Представляет числа в виде строк цифр. N и M - это две строки одинаковой длины.

Давайте наберем N цифр как N _k , где N ₀ является последним ( крайняя справа) цифра.

Набор M ₀ = N ₀ - 1, M ₁ = N ₁ + 1, M _i = N _i в противном случае. Сумма цифр M остается такой же, как в N , потому что вы только что переместили 1 из одной цифры в другую, но теперь M > * +1049 * N . * * тысяча пятьдесят-одна

Конечно, этот трюк не работает, если N ₀ = 0 или если N ₁ = 9. В этом случае , перейти к N ₁ и N ₂ для передачи 1 и т. д.

В качестве упражнения докажите, что M , созданный таким образом, действительно является наименьшим числом, удовлетворяющим условиям. (Или опровергнуть - я могу ошибаться, особенно в случае N ₀ = 0, хотя я не понимаю, где я ошибаюсь.)