Count Digits

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

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

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

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

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

+10

Для заданного неотрицательного целого числа n верни количество цифр в его записи в десятичной системе счисления без ведущих нулей. Ноль записывается одной цифрой 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.

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

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

Подсказки

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

Открыто 0 из 3

Решение

Каждое целочисленное деление на 10 удаляет одну цифру. Подсчитай количество делений, пока не останется одна цифра, затем прибавь единицу за эту цифру. Ошибки возникают на границах: у 0 одна цифра, а формула с логарифмом не работает для 0 и для чисел чуть меньше больших степеней десяти.

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

Идея

Ваш язык уже записывает n в десятичной системе счисления. Запросите эту строку и посчитайте её символы: 4096 становится "4096", это четыре символа, а 0 становится "0", поэтому для нуля не нужен особый случай.

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

Алгоритм

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

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

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

Идея

Начни счёт с 1 и дели на 10, пока n ≥ 10, прибавляя 1 при каждом делении. Начало с 1 означает, что у каждого числа есть как минимум одна цифра, что точно соответствует правилу для 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, где логарифм равен минус бесконечности, и для 10^15-1, где при вычислениях с двойной точностью логарифм округляется ровно до 15, и формула выдаёт 16 цифр.
Деление с остатком в JavaScript, Lua, PHP или R, где / сохраняет дробную часть. Тогда цикл, выполняющийся, пока n > 0, для числа 4096 выполняется 328 раз. Используй Math.floor, math.floor, intdiv или %/%.
Научная нотация в строковом варианте. R записывает as.character(1e5) как "1e+05"; используй sprintf("%.0f", n). В Lua 5.3 и более поздних версиях tostring(4096.0) сохраняет .0; используй string.format("%d", n).

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

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

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

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

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

Как посчитать цифры отрицательного числа?

Сначала возьмите абсолютное значение, затем считайте как обычно. String(-42) содержит три символа, потому что знак минуса — не цифра. Для наименьшего 32-битного целого числа возьмите абсолютное значение в 64-битном типе, поскольку оно не помещается в 32 бита.

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

Тест #1

Тест #2

Тест #3

Аргумент

n = 4096

Ожидаемый вывод