Sum of Digits

Q: Какова временная сложность суммирования цифр числа?

Один шаг на каждую цифру, то есть O(d) , где d — количество цифр. Число n содержит примерно log10(n) + 1 цифр, поэтому ту же оценку часто записывают как O(log n) . Для 32-битного целого числа это не более 10 шагов.

Q: Какая версия лучше: строковая или арифметическая?

Оба варианта имеют сложность O(d) и оба правильны. Строковый вариант во многих языках короче, но создает копию цифр. Арифметический вариант использует O(1) дополнительной памяти и показывает интервьюеру, что ты знаешь, как % 10 и / 10 разбирают число на части, что пригодится в задачах на палиндромы и обращение порядка цифр.

НовичокМатематика и моделирование

+10

Тебе дано неотрицательное целое число n. Верни сумму его десятичных цифр. Например, цифры числа 482 — это 4, 8 и 2, поэтому ответ — 14.

Функция

sumOfDigits(n: integer) → integer

ninteger: неотрицательное целое число, цифры которого ты складываешь
Возвращаетinteger: сумма десятичных цифр числа n

Ограничения

0 ≤ n ≤ 2³¹-1

Примеры

Ввод: n = 9045
Вывод: 18
Пояснение: Цифры числа 9045 — это 9, 0, 4 и 5, а 9 + 0 + 4 + 5 = 18. Ноль ничего не прибавляет, но всё равно считается цифрой.

Ввод: n = 7
Вывод: 7
Пояснение: Однозначное число равно сумме своих цифр, поэтому 7 даёт 7.

+15 скрытых тестов при отправке

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Число не выдает свои цифры по одной; нужно разобрать его на части. Можно преобразовать его в текст и считывать символы или использовать две арифметические операции, которые отделяют последнюю цифру: n % 10 возвращает ее, а целочисленное деление на 10 удаляет ее. Оба способа требуют по одному шагу на цифру, обозначенную ниже как d, причем здесь d ≤ 10. Арифметический способ не требует дополнительной памяти.

Прочитайте цифры как текст

Идея

Когда вы записываете число, его цифры уже видны. Преобразуйте n в его десятичное представление: 9045 превращается в четыре символа — 9, 0, 4 и 5, затем пройдите по символам и сложите значения каждого из них.

Символ — это ещё не число. Символ '4' хранится как код 52, поэтому преобразуйте его в число или вычтите код '0': '4' - '0' = 4. Коды символов-цифр идут подряд, поэтому это вычитание работает для всех десяти цифр.

Текст состоит из d символов, по одному на каждую цифру, поэтому цикл занимает O(d) времени, а сам текст — O(d) дополнительной памяти.

Алгоритм

Преобразуйте n в его десятичное текстовое представление.
Установите total = 0.
Для каждого символа прибавьте его значение цифры к total.
Верните total.

def sumOfDigits(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

Получите последнюю цифру с помощью % 10

Идея

Число можно разложить на цифры без использования текста. Остаток от деления на 10 — это последняя цифра: 9045 % 10 = 5. Целочисленное деление на 10 отбрасывает эту цифру: 9045 / 10 = 904, если отбросить дробную часть. Повторяйте эту пару действий, и цифры будут извлекаться справа налево.

Для 9045: прибавляем 5 и оставляем 904, прибавляем 4 и оставляем 90, прибавляем 0 и оставляем 9, прибавляем 9 и оставляем 0. Цикл останавливается на 0, а сумма равна 18. При n = 0 цикл ни разу не выполняется, и ответ равен 0, что верно.

На каждом шаге удаляется одна цифра, поэтому всего выполняется d шагов, время работы составляет O(d), а в памяти хранятся только два целых числа — требуется O(1) памяти. Каждое промежуточное значение меньше n, поэтому переполнение невозможно.

Алгоритм

Установи total = 0.
Пока n > 0, добавляй n % 10 к total.
Раздели n на 10, отбросив дробную часть.
Когда n достигнет 0, верни total.

def sumOfDigits(n):
    total = 0
    while n > 0:
        total += n % 10  # last digit
        n //= 10         # drop the last digit
    return total

Ловушки и крайние случаи

Цикл короткий, а ошибки связаны с типами и минимальным входным значением.

Использование / там, где язык выполняет обычное деление. В JavaScript, TypeScript, Lua, PHP и R выражение 9045 / 10 даёт 904.5, и цикл затем складывает дробные числа. Округляй вниз с помощью Math.floor или math.floor; в Python используй //, в Dart — ~/, в PHP — intdiv, в R — %/%.
Сложение символов вместо цифр. Символ '7' имеет код 55, а не 7. Вычти '0' или сначала преобразуй символ в число.
Цикл с условием n >= 10. Тогда цикл остановится, когда старшая цифра всё ещё находится в n, и никогда не прибавит её, поэтому для 9045 получится 9 вместо 18. Выполняй цикл, пока n > 0; при n = 0 он также вернёт 0.
Вывод больших чисел в виде текста в R. as.character(100000) даёт "1e+05", а не шесть цифр числа. Используй format(n, scientific = FALSE).

Частые вопросы4

Какова временная сложность суммирования цифр числа?

Один шаг на каждую цифру, то есть O(d), где d — количество цифр. Число n содержит примерно log10(n) + 1 цифр, поэтому ту же оценку часто записывают как O(log n). Для 32-битного целого числа это не более 10 шагов.

Как получить цифры числа, не преобразуя его в строку?

Используйте остаток от деления и целочисленное деление на 10. n % 10 — это последняя цифра, а деление n на 10 с отбрасыванием остатка удаляет эту цифру. Повторяйте, пока n не достигнет 0, и вы переберёте все цифры справа налево.

Что такое цифровой корень числа?

Это число получается, если снова и снова складывать цифры, пока не останется одна цифра: 9045 дает 18, затем 9. Для положительного n оно равно 1 + (n-1) % 9, потому что при делении на 9 любое число дает тот же остаток, что и сумма его цифр.

Какая версия лучше: строковая или арифметическая?

Оба варианта имеют сложность O(d) и оба правильны. Строковый вариант во многих языках короче, но создает копию цифр. Арифметический вариант использует O(1) дополнительной памяти и показывает интервьюеру, что ты знаешь, как % 10 и / 10 разбирают число на части, что пригодится в задачах на палиндромы и обращение порядка цифр.

Python

def sumOfDigits(n):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

n = 9045

Ожидается