Armstrong Number

Q: Какова временная сложность проверки числа Армстронга?

В числе n примерно log n цифр, здесь не более 10. Извлечение цифр и поиск каждой степени в таблице из десяти элементов занимает время O(log n) и память O(1) . Повторное вычисление d^k в цикле для каждой цифры даёт сложность O(log² n) — для такого размера всё ещё быстро.

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

+10

Положительное целое число является числом Армстронга, если оно равно сумме своих цифр, каждая из которых возведена в степень, равную количеству цифр в этом числе. В числе 153 три цифры, и 1^3 + 5^3 + 3^3 = 153, поэтому это число Армстронга. Напишите функцию, которая получает n и возвращает true, если это число Армстронга, и false в противном случае.

Функция

isArmstrong(n: integer) → boolean

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

Ограничения

1 ≤ n ≤ 10⁹

Примеры

Ввод: n = 153
Вывод: true
Пояснение: Число 153 состоит из 3 цифр, поэтому каждую цифру возводят в куб: 1 + 125 + 27 = 153. Сумма дает исходное число, поэтому ответ — true.

Ввод: n = 10
Вывод: false
Пояснение: В числе 10 2 цифры, поэтому квадрат возводится для каждой цифры: 1 + 0 = 1, что не равно 10. Ответ — false.

Ввод: n = 9474
Вывод: true
Пояснение: Для 4 цифр степень равна 4: 6561 + 256 + 2401 + 256 = 9474, то есть само число, поэтому ответ — true.

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

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

Между 1 и 10^9 находится всего 31 число Армстронга. Сможешь перечислить их все, не проверяя миллиард чисел по одному?

Подсказки

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

Открыто 0 из 3

Решение

Определение и есть алгоритм: найти, сколько цифр содержит n, возвести каждую цифру в эту степень, сложить результаты и сравнить с n. Подводные камни — в числах. Показатель степени — это количество цифр именно в этом n, а не фиксированное число 3, и сумма может превысить предел 32-битного целого числа: для 999999999 она равна 9 × 9^9 = 3486784401.

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

Идея

Десятичная строка числа n содержит обе необходимые вам вещи. Её длина — это показатель степени k, а её символы — цифры. Для 9474 строка содержит 4 символа, поэтому вы складываете 9^4 + 4^4 + 7^4 + 4^4.

Преобразуйте каждый символ обратно в цифру, возведите её в степень k и прибавьте к текущей сумме. n является числом Армстронга тогда и только тогда, когда полученная сумма равна n.

Храните сумму в 64-битном целом числе. n помещается в 32 бита, но сумма не обязательно: для 999999999 получается 3486784401, что превышает 32-битный предел 2147483647. Возведение в степень с помощью цикла из k умножений занимает k шагов на каждую цифру, поэтому проверка выполняется за O(k²), где k примерно равно log n. В данном случае это не более 100 умножений, а строка занимает k символов памяти.

Алгоритм

Преобразуй n в десятичную строку и пусть k будет её длиной.
Установи значение 64-битной переменной total равным 0.
Для каждого символа преобразуй его в цифру d и прибавь d^k к total, перемножая целые числа, а не вызывая функцию возведения в степень с плавающей точкой.
Верни, равно ли total значению n.

def isArmstrong(n):
    digits = str(n)
    k = len(digits)
    total = 0
    for ch in digits:
        total += int(ch) ** k
    return total == n

Отделите цифры и найдите их степени

Идея

Одну и ту же задачу можно решить только с помощью арифметики, без строки. m % 10 — последняя цифра числа m, а целочисленное деление на 10 отбрасывает её, поэтому цикл, который делит число на 10, пока от него ничего не останется, подсчитывает цифры. 9474 превращается в 947, 94, 9, 0: четыре шага, значит, k = 4.

Цифр всего десять, поэтому перед сложением чего-либо создай таблицу powers[d] = d^k для d от 0 до 9. Тогда для каждой цифры понадобится одно обращение к таблице вместо k умножений. Проверка будет выполняться за O(log n), а таблица имеет фиксированный размер — десять элементов, то есть занимает O(1) места.

Второй цикл снова извлекает цифры и прибавляет powers[m % 10] к общей сумме. Каждое слагаемое неотрицательно, поэтому сумма никогда не уменьшается, а как только она превысит n, ответом будет false. Для 999999999 это происходит после трёх цифр: 3 × 387420489 = 1162261467. Для таблицы всё ещё нужны 64 бита, потому что n = 10^9 состоит из десяти цифр, а 9^10 = 3486784401.

Алгоритм

Подсчитайте количество цифр в n, деля копию на 10, пока она не достигнет 0; назовите это количество k.
Заполните powers[d] = d^k для каждой цифры d от 0 до 9, используя 64-битные целые числа.
Снова делите свежую копию n на 10, на каждом шаге добавляя powers[m % 10] к total.
Если total превысит n, сразу верните false.
После последней цифры верните результат проверки, равно ли total значению n.

def isArmstrong(n):
    # Count the digits: k is the exponent.
    k = 0
    m = n
    while m > 0:
        k += 1
        m //= 10
    # powers[d] = d^k for the ten possible digits.
    powers = [d ** k for d in range(10)]
    total = 0
    m = n
    while m > 0:
        total += powers[m % 10]
        if total > n:
            return False  # the total only grows
        m //= 10
    return total == n

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

Формула короткая, поэтому ошибки возникают из-за окружающих её чисел.

Фиксированный показатель степени 3. Такой код принимает 153 и 370, но отвергает 9474, а также отвергает каждое однозначное число больше 1, поскольку 7^3 = 343.
32-битная сумма. Для 999999999 сумма равна 3486784401, и элемент таблицы 9^10 — это то же число. В C это переполнение приводит к неопределённому поведению, Java и C# дают отрицательное число, а отладочная сборка Rust вызывает панику. Используйте long, long long или i64.
Степени с плавающей точкой. pow в C и Math.pow в Java возвращают значение типа double. Некоторые среды выполнения C возвращали значение чуть меньше целого числа, например 24.999... для 5^2, которое при приведении типа усекается до 24. Вместо этого перемножайте целые числа в цикле.
Сравнение с неправильным значением. Циклы по цифрам делят n, пока оно не станет равным 0, поэтому работайте с копией и сравнивайте сумму с исходным значением.
Научная нотация. В R as.character(1e9) — это "1e+09", то есть пять символов, поэтому решение на основе строк в R форматирует значение с помощью sprintf("%.0f", n).

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

Что такое число Армстронга?

Число Армстронга, также называемое нарциссическим числом, равно сумме собственных цифр, каждая из которых возведена в степень, равную количеству цифр в числе. 153 — такое число, потому что 1^3 + 5^3 + 3^3 = 153, а 9474 — потому что 9^4 + 4^4 + 7^4 + 4^4 = 9474. Любое однозначное число подходит, поскольку d^1 = d.

Сколько существует чисел Армстронга?

В системе счисления с основанием 10 ровно 88 положительных чисел, равных сумме степеней своих цифр, и наибольшее из них состоит из 39 цифр. Список конечен, потому что число с k цифрами не меньше 10^(k-1), а сумма степеней его цифр не больше k × 9^k, и начиная с 61 цифры сумма уже никогда не сможет догнать число. Между 1 и 10^9 таких чисел 31.

Почему для проверки числа Армстронга требуется 64-битное целое число?

Входное значение помещается в 32 бита, но сумма цифр, возведённых в степень, может в несколько раз превышать само число. Для 999999999 получаем 9 × 9^9 = 3486784401, что больше 2^31-1 = 2147483647. Здесь 32-битная сумма переполняется, поэтому храните сумму и степени в 64-битном типе.

Какова временная сложность проверки числа Армстронга?

В числе n примерно log n цифр, здесь не более 10. Извлечение цифр и поиск каждой степени в таблице из десяти элементов занимает время O(log n) и память O(1). Повторное вычисление d^k в цикле для каждой цифры даёт сложность O(log² n) — для такого размера всё ещё быстро.

Python

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

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

Случай 1

Случай 2

Случай 3

Ввод

n = 153

Ожидается

true