Для решения сегодняшней задачи мы с вами вспомним школьную программу, а именно — как складывать числа столбиком.
Сложность: 🟢 Легкая
ℹ️ Описание
Дано большое целое число, представленное в виде целочисленного массива digits, где digits[i] — это i-я цифра целого числа. Цифры упорядочены от наиболее значимого к наименее значимому, слева направо. Число не содержит ведущих нулей.
Увеличьте число на единицу и верните полученный массив цифр.
⚠️ Ограничения
— В массиве цифр может быть от 1 до 100 элементов
— В массиве содержатся только цифры от 0 до 9
— Число не содержит ведущих нулей
1️⃣ Пример
Входящие данные
Ответ
2️⃣ Пример
Входящие данные
Ответ
3️⃣ Пример
Входящие данные
Ответ
✅ Решение
Чтобы решить задачу, нужно реализовать подход со сложением чисел в столбик.
Каждая цифра в массиве представляет собой один разряд числа. Сначала нужно прибавить к младшему разряду (крайнему справа) единицу согласно условиям задачи, а потом следовать простому алгоритму.
1. Если сумма меньше 10, то вместо текущего разряда нужно записать эту сумму.
2. Если сумма больше 10, то вместо текущего разряда нужно записать остаток от деления суммы на 10, а к следующему разряду прибавить единицу. Для всех последующих разрядов нужно повторить эти же действия.
3. Если мы обрабатываем старший разряд (крайний слева) и сумма больше 10, то в текущий разряд мы добавляем остаток от деления суммы на 10 и добавляем еще один разряд, в который записываем единицу.
Перебирать исходный массив будем справа налево, добавляя результат вычислений для каждого разряда в конец результирующего массива. В результате мы получим инвертированный массив, поэтому в конце остается только развернуть его относительно центра.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
O(n) — так как мы дважды итерируемся по всему массиву.
По памяти
O(n) — так как мы выделяем память для хранения результирующего массива.
#arrays #easy #math