Плюс один

Легкая

easy , math , array

28 January 2024

Описание задачи #

Дано большое целое число, представленное в виде целочисленного массива digits, где digits[i] — это i-я цифра целого числа. Цифры упорядочены от наиболее значимого к наименее значимому, слева направо. Число не содержит ведущих нулей.

Увеличьте число на единицу и верните полученный массив цифр.

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

В массиве цифр может быть от 1 до 100 элементов
В массиве содержатся только цифры от 0 до 9
Число не содержит ведущих нулей

Примеры #

Входные данные: [1,2,3]

Ответ: [1,2,4]
Входные данные: [2,2,9]

Ответ: [2,3,0]
Входные данные: [9]

Ответ: [1, 0]

Решение #

Чтобы решить задачу, нужно реализовать подход со сложением чисел в столбик.

Каждая цифра в массиве представляет собой один разряд числа. Сначала нужно прибавить к младшему разряду (крайнему справа) единицу согласно условиям задачи, а потом следовать простому алгоритму.

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

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

Реализация #

package plus_one

func plusOne(digits []int) []int {
	res := make([]int, 0, len(digits)+1)
	temp := 0

	for i := len(digits) - 1; i >= 0; i-- {
		digit := digits[i]
		temp += digit

		if i == len(digits)-1 {
			temp += 1
		}

		if temp < 10 {
			res = append(res, temp)
			temp = 0
			continue
		}

		res = append(res, temp%10)
		temp = 1
	}

	if temp != 0 {
		res = append(res, temp)
	}

	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}

	return res
}

export const plusOne = (digits: number[]): number[] => {
    const res: number[] = []
    let temp = 0

    for (let i = digits.length - 1; i >= 0; i--) {
        const digit = digits[i]
        temp += digit

        if (i == digits.length - 1) {
            temp += 1
        }

        if (temp < 10) {
            res.push(temp)
            temp = 0
            continue
        }

        res.push(temp % 10)
        temp = 1
    }

    if (temp != 0) {
        res.push(temp)
    }

    for (let i = 0, j = res.length - 1; i < j; i++, j--) {
        const tmp = res[i]
        res[i] = res[j]
        res[j] = tmp
    }

    return res
}

Оценка сложности #

По времени

O(n) — так как мы дважды итерируемся по всему массиву.

По памяти

O(n) — так как мы выделяем память для хранения результирующего массива.

Оригинал задачи на Leetcode

Algorithmics