Найдите следующее число, складывая натуральные числа в порядке чередования индексов от последнего
Для заданной числовой строки S размера N задача состоит в том, чтобы найти число, образованное добавлением чисел 1 , 2 , 3 , … до бесконечности к каждой альтернативной цифре данной числовой строки S (начиная с последней позиции). В любой момент, если результат сложения не является одной цифрой, выполняйте повторное сложение цифр до тех пор, пока результат не станет одной цифрой.
Примеры:
Input: S = “1345”
Output: 1546
Explanation:
Adding 1 to the last digit i.e., 5 will become 6 which modifies the string to “1346”.
Adding 2 to the second last digit i.e., 3 will become 5 which modifies the string to “1546”.
After the above steps, the resultant string formed is “1546”.Input: S = “789”
Output: 981
Подход: Идея решения этой проблемы лежит в части повторного сложения. На самом деле нет необходимости многократно выполнять сложение, пока не останется одна цифра. Вместо этого выполните число % 9 . Если число %9 равно 9 , то сумма цифр будет равна 9, иначе сумма цифр будет равна числу %9 . Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте переменные temp и add_number равными 0 , чтобы сохранить изменяемую позицию и добавляемое число.
- Инициализируйте результат строковой переменной как пустую строку, чтобы сохранить результат.
- Переберите диапазон [len-1, 0], где len — длина строки, используя переменную i , и выполните следующие шаги:
- Инициализируйте цифру переменной как цифру в текущей позиции в строке.
- Если temp%2 равно 0 , увеличьте значение add_number на 1 и добавьте его к переменной digit.
- Если цифра больше, чем равна 10 , установите значение цифры как цифра% 9 , а если все еще цифра равна 0 , то установите ее значение как 9.
- Добавьте переменную цифру к переменному результату в начале.
- После выполнения вышеуказанных шагов выведите значение результата в качестве ответа.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(1)