Плюс один

Источник: https://leetcode.com/problems/plus-one/

Дан не пустой массив десятичных чисел, которые представляют собой неотрицательное число. Увеличить это число на 1.

Старший разряд числа находится в голове массива (в индексе 0)б каждая чейка массива содержит число от 0 до 9.

Данное представление числа не имеет в начале нулей, кроме случая, когда массив и представляет собой 0.

Пример 1:

Дано: digits = [1,2,3]
Результат: [1,2,4]
Пояснение: Исходный массив кодирует число 123. 123+1=124.

Пример 2:

Дано: digits = [4,3,2,1]
Результат: [4,3,2,2]

Пример 3:

Дано: digits = [0]
Результат: [1]

Ограничения:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

Идея решения

Мы все в школе учились складыватьв столбик, когда к младшему разряду числа добавляется  младший разряд другого числа. Если их сумма меньше 9, то в младший разряд результирующего числа записывается эта сумма. Если же сумма больше 9, то в младший разряд записываем остаток от деления на 10, а целочисленную часть от деления на 10 переносим к сумме чисел следующего разряда.

Например, 69+23. Младшие разряды: 9+3=12. В младший разряд записываем 2 (остаток от деления 12 на 10). Целочисленная часть деления 12 на 10 равна 1. И она переходит к сумме следущих разрядов, то есть не просто 6+2, а 6+2+1=9. Это число меньше 9, поэтому мы его и записываем во второй разряд.

Итого: 69+23 = 92.

Если число такое большое, что не помещается в стандартный тип данных, то его представляют в виде строки, массива, списка. И операции проводятся на этой структуре, сумма и вычитание делаются поразрядно.

Имплементация

class Solution {
    public int[] plusOne(int[] digits) {
        
        int n = digits.length;
        for(int i=n-1; i>=0; i--) { // идем от младших разрядов к старшим
            if(digits[i] < 9) { // цифра в этом разряде меньше 9, значит +1 не даст переполнения
                digits[i]++; // увеличиваем цифру в разряде на 1
                return digits; // переполнения нет, другие разряды не меняются, выходим
            }
        
            digits[i] = 0; // переполнение 9+1=10. Записываем остаток от деления на 10
            // целая часть от деления на 10 = 1,
            // эта единичка будет суммирована со следующим более старшим разрядом
            // поэтому продолжаем проходить по массиву в направлении нулевого элемента
        }
   
// мы до сих пор не вышли, значит переполнение произошло в самом старшем разряде,
// который находится в индексе 0.
// Значит, добавляется дополнительный разряд перед нулевым, куда мы записываем 1.
        int[] newNumber = new int [n+1];
        newNumber[0] = 1; // остальные значения инициализированы 0 по умолчанию
    
        return newNumber;
    }
}