Count Digits

Q: Почему у 0 одна цифра?

Ноль записывается одним символом 0 , поэтому его десятичная запись состоит из одной цифры. Код, который подсчитывает деления, пока число больше 0, для 0 не выполняется и возвращает 0. Если начать счётчик с 1 и делить, пока число не меньше 10, это обработает случай без особых условий.

Q: Можно ли использовать log10, чтобы посчитать количество цифр в числе?

Для положительного n количество цифр равно floor(log10(n)) + 1 , но логарифм вычисляется с плавающей точкой. Для 0 он не определён, а вблизи степени десяти результат может округлиться в неверную сторону: log10(10^15-1) в двойной точности возвращает ровно 15. Целочисленное деление каждый раз даёт точный ответ.

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

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

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

+10

Напишите функцию, которая получает неотрицательное целое число n и возвращает количество цифр в его записи в системе счисления с основанием 10 без ведущих нулей. Ноль записывается одной цифрой 0, поэтому в нём одна цифра.

Функция

countDigits(n: integer) → integer

ninteger: неотрицательное целое число для измерения
Возвращаетinteger: количество цифр после десятичной точки в n

Ограничения

0 ≤ n ≤ 2³¹-1

Примеры

Ввод: n = 4096
Вывод: 4
Пояснение: Целочисленное деление на 10 превращает 4096 в 409, 40 и 4. Это удаляет три цифры и оставляет одну, поэтому ответ — 4.

Ввод: n = 0
Вывод: 1
Пояснение: 0 записывается одной цифрой. Цикл, который считает, пока число больше 0, здесь никогда не запустится и вернёт 0 вместо 1.

Ввод: n = 100
Вывод: 3
Пояснение: Нули — это тоже цифры: 100 записывается как 1, 0, 0, поэтому ответ — 3.

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

Дополнительный вопрос

Можете ли вы посчитать цифры без цикла, который выполняется один раз для каждой цифры, например с помощью бинарного поиска по степеням десяти?

Подсказки

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

Открыто 0 из 3

Решение

Количество цифр — это число раз, которое можно разделить на 10, прежде чем останется одна цифра, плюс эта цифра. Идея умещается в одну строку; трудности — в крайних случаях. У 0 одна цифра, количество меняется между 9 и 10, а формула на основе логарифма не работает для 0 и, при вычислениях с плавающей точкой, немного ниже больших степеней десяти.

Запишите число текстом и посчитайте количество символов

Идея

Ваш язык уже умеет записывать n в десятичной системе счисления. Попросите его представить число в виде строки и посчитайте символы: 4096 превращается в "4096" — четыре символа. 0 превращается в "0" — один символ, поэтому для нуля не нужен отдельный случай.

Преобразование выполняет деление на 10 внутри библиотеки, один раз на каждую цифру, поэтому трудоёмкость составляет O(log n). В строке содержится один символ на каждую цифру, то есть она занимает O(log n) дополнительной памяти — здесь не более 10 символов.

Формат должен быть обычным десятичным. В R выражение as.character(1e5) возвращает "1e+05" — пять символов для шестизначного числа, поэтому задайте формат с помощью sprintf("%.0f", n). В Lua 5.3 и более поздних версиях tostring(4096.0) сохраняет .0, тогда как string.format("%d", n) записывает целое число во всех версиях.

Алгоритм

Преобразуй n в десятичную строку с помощью функции, которая никогда не переключается на экспоненциальную запись.
Посчитай количество символов в строке.
Верни это количество. Для 0 строка — "0", поэтому ответ — 1, дополнительная проверка не нужна.

def countDigits(n):
    return len(str(n))

Делите на 10, пока не останется одна цифра

Идея

Целочисленное деление на 10 удаляет последнюю цифру: 4096 / 10 — это 409. Каждое деление убирает одну цифру, поэтому ответ — количество делений, необходимых, чтобы получить однозначное число, плюс один для этой последней цифры. Для 4096 нужны три деления (409, 40, 4), значит, в нём 4 цифры.

Начни счёт с 1 и дели, пока n ≥ 10. Начальное значение 1 означает, что у любого числа есть как минимум одна цифра, что верно и для 0. Вариант, который обычно пишут первым, — считать от 0, пока n > 0; он возвращает 0 для n = 0, поэтому нужна отдельная проверка.

Цикл выполняется один раз для каждой цифры после первой — не более 9 раз для 2147483647, поэтому время работы составляет O(log n). Он хранит один счётчик и изменяет собственную копию n, поэтому дополнительная память составляет O(1).

Алгоритм

Установите count = 1 для цифры, которая есть всегда.
Пока n ≥ 10, делите n на 10 с помощью целочисленного деления и прибавляйте 1 к count.
Когда останется одна цифра, верните count.

def countDigits(n):
    count = 1  # every number, 0 included, has at least one digit
    while n >= 10:
        n //= 10
        count += 1
    return count

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

Все ошибки в этой задаче связаны с граничными случаями.

Подсчёт с 0 при условии n > 0. Это верно для любого положительного числа, а при n = 0 возвращается 0.
Использование floor(log10(n)) + 1. Этот способ не работает для 0, где логарифм равен минус бесконечности, а для больших значений, чуть меньших степени десяти, даёт сбой: при двойной точности log10(10^15-1) округляется ровно до 15, поэтому формула выдаёт 16 цифр вместо 15.
Вещественное деление в цикле, который выполняется, пока n > 0. В JavaScript, Lua, PHP и R оператор / сохраняет дробную часть, поэтому 4096 уменьшается, приближаясь к 0, в течение 328 шагов, прежде чем достигнет его. Используйте Math.floor, math.floor, intdiv или %/%.
Научная нотация в строковом варианте: R записывает 100000 как "1e+05".
Учёт знака минус как цифры. В этом примере входные данные никогда не бывают отрицательными, но String(-42) содержит три символа, поэтому в версии для отрицательных чисел сначала берут абсолютное значение.

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

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

Делите число на 10 с помощью целочисленного деления, пока не останется одна цифра, подсчитывая деления, и прибавьте 1 за последнюю цифру. 4096 превращается в 409, 40, 4: три деления, значит, 4 цифры. Цикл использует дополнительную память O(1).

Почему у 0 одна цифра?

Ноль записывается одним символом 0, поэтому его десятичная запись состоит из одной цифры. Код, который подсчитывает деления, пока число больше 0, для 0 не выполняется и возвращает 0. Если начать счётчик с 1 и делить, пока число не меньше 10, это обработает случай без особых условий.

Можно ли использовать log10, чтобы посчитать количество цифр в числе?

Для положительного n количество цифр равно floor(log10(n)) + 1, но логарифм вычисляется с плавающей точкой. Для 0 он не определён, а вблизи степени десяти результат может округлиться в неверную сторону: log10(10^15-1) в двойной точности возвращает ровно 15. Целочисленное деление каждый раз даёт точный ответ.

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

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

Python

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

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

Случай 1

Случай 2

Случай 3

Ввод

n = 4096

Ожидается