Happy Number

Q: Почему процесс всегда достигает 1 или цикла?

Число с d цифрами переходит в число не больше 81 × d , поэтому большие числа быстро уменьшаются: любое начальное число не больше 2^31-1 после одного шага становится меньше 1000, а число меньше 1000 переходит в число не больше 243. Последовательность ограничена менее чем 1000 значениями, поэтому какое-то значение обязательно встретится повторно, после чего начнётся цикл. 1 — единственное число, которое переходит само в себя.

Q: Какова временная сложность задачи «Счастливое число»?

На первом шаге считываются O(log n) цифры числа n . Все последующие значения меньше 1000, а последовательность повторяется не более чем через 20 чисел, поэтому общее время работы составляет O(log n) . Вариант с хеш-множеством хранит посещённые числа; вариант Флойда использует O(1) памяти.

ЛегкоБыстрый и медленный указатели Хеширование

+10

Начни с положительного целого числа n и снова и снова заменяй его суммой квадратов его цифр. Например, 12 превращается в 1² + 2² = 5. Если в результате этого процесса получается 1, то n — счастливое число; иначе числа бесконечно повторяются по циклу, в котором никогда не встречается 1. Верни true, если n — счастливое число, и false, если это не так.

Функция

isHappy(n: integer) → boolean

ninteger: положительное целое число для проверки
Возвращаетboolean: true, если повторение суммы квадратов цифр приводит к 1; false, если повторяется бесконечно

Ограничения

1 ≤ n ≤ 2³¹-1

Примеры

Ввод: n = 7
Вывод: true
Пояснение: 7 превращается в 49, затем 4² + 9² = 97, затем 130, затем 10, затем 1. Процесс достигает 1, поэтому 7 — счастливое число.

Ввод: n = 2
Вывод: false
Пояснение: 2 превращается в 4, 16, 37, 58, 89, 145, 42, 20, а затем снова в 4. После этого те же восемь чисел повторяются бесконечно и никогда не достигают 1.

Ввод: n = 100
Вывод: true
Пояснение: 1² + 0² + 0² = 1, поэтому 100 достигает 1 за один шаг.

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

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

Как быстро посчитать счастливые числа от 1 до 10^6, повторно используя ответы для чисел меньше 1000, вместо того чтобы каждый раз начинать вычисления с нуля?

Подсказки

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

Открыто 0 из 3

Решение

Последовательность не может бесконечно уходить в бесконечность. Число из 10 цифр переходит не более чем в 10 × 81 = 810, а число меньше 1000 — не более чем в 3 × 81 = 243, поэтому после одного шага последовательность остаётся среди значений меньше 1000 и должна достичь 1 или повторить число. Это превращает задачу в обнаружение цикла: запоминайте, что уже видели, или запустите медленного и быстрого бегунов и проверьте, встретятся ли они.

Запомни каждое число, которое ты видел

Идея

Проходите последовательность и сохраняйте каждое число в хеш-множестве. Прежде чем перейти к следующему числу, проверьте, есть ли оно уже в множестве. Для 2 множество заполняется числами 2, 4, 16, 37, 58, 89, 145, 42 и 20, а следующее значение — 4, которое уже есть в множестве: последовательность замкнулась в цикл, не достигнув 1, поэтому 2 не является счастливым числом. Достижение 1 завершает проход со значением true.

Это верно, потому что следующее число зависит только от текущего. Как только число повторяется, всё, что следует за ним, повторяется в точности, поэтому новые числа появиться не могут, а 1 уже не встретится.

Проход короткий. На первом шаге считываются O(log n) цифр числа n, а каждое последующее значение меньше 1000; в такой последовательности до достижения 1 или повторения не встречается более 20 различных чисел. Множество хранит эти числа. В коде C в качестве множества используется массив флагов из 1000 элементов, и запись начинается после первого шага, когда все значения становятся меньше 1000.

Алгоритм

Создай пустое хеш-множество seen.
Пока n не равно 1, верни false, если n содержится в seen.
В противном случае добавь n в seen и замени n суммой квадратов его цифр.
Когда цикл завершится, n равно 1: верни true.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False  # back at an earlier number: a loop without 1
        seen.add(n)
        n = digitSquareSum(n)
    return True

Быстрые и медленные указатели (алгоритм Флойда для обнаружения цикла)

Идея

Представь каждое число как узел с одной стрелкой, указывающей на сумму квадратов его цифр. Следуя по стрелкам от n, можно либо прийти к 1, стрелка которой указывает обратно на 1, либо попасть в цикл. Так устроен связный список, который может содержать цикл, и алгоритм Флойда обнаруживает цикл, ничего не сохраняя: slow проходит один шаг за раунд, а fast — два.

Если цикл не содержит 1, оба бегуна в итоге будут двигаться по нему, и каждый раунд fast будет продвигаться на один шаг дальше slow, поэтому разрыв будет уменьшаться на один, пока они не окажутся на одном и том же числе. Для 2 они встречаются на 42 после семи раундов. Если последовательность доходит до 1, fast приходит туда первым и остается там, потому что сумма для 1 равна 1. Поэтому остановись, когда fast станет равен 1 или бегуны встретятся, и проверь, равен ли fast 1.

Для 7 slow проходит 7, 49, 97, а fast — 49, 130, 1, и цикл останавливается, когда fast оказывается на 1. Число раундов не превышает небольшое кратное длины последовательности, поэтому время работы такое же, как у версии с множеством, а для памяти нужны два целых числа.

Алгоритм

Напишите вспомогательную функцию, которая возвращает сумму квадратов цифр числа.
Установите slow = n, а значение fast установите равным числу, следующему за n на один шаг.
Пока fast не равно 1 и slow не равно fast, перемещайте slow на один шаг, а fast — на два шага.
Верните результат проверки, равно ли fast 1.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    slow = n
    fast = digitSquareSum(n)
    # fast moves two steps for every step of slow; they meet only inside a loop.
    while fast != 1 and slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    return fast == 1

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

Арифметика для цифр проста. Большинство ошибок связано с тем, когда останавливается цикл.

Цикл продолжается, пока значение не станет равным 1, без другого условия выхода. Для 2 этот цикл никогда не завершится.
Запустить slow и fast с одного и того же числа и проверить slow != fast до первого шага. Цикл ни разу не выполнится, и число 7 окажется несчастливым. Запустите fast на один шаг впереди или переместите оба указателя перед первым сравнением.
Возвращать slow == 1 в версии с алгоритмом Флойда. fast достигает 1 первым, и цикл сразу останавливается, в то время как slow все еще может быть равен 97.
Складывать цифры вместо их квадратов или возводить в квадрат всё число. Для 12 следующее значение — 1² + 2² = 5, а не 3 и не 144.
Объявлять n несчастливым каждый раз, когда указатели встречаются. 1 отображается в само себя, поэтому указатели также встречаются на 1; проверьте, где они встретились, или остановитесь, как только fast станет равен 1.

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

Почему процесс всегда достигает 1 или цикла?

Число с d цифрами переходит в число не больше 81 × d, поэтому большие числа быстро уменьшаются: любое начальное число не больше 2^31-1 после одного шага становится меньше 1000, а число меньше 1000 переходит в число не больше 243. Последовательность ограничена менее чем 1000 значениями, поэтому какое-то значение обязательно встретится повторно, после чего начнётся цикл. 1 — единственное число, которое переходит само в себя.

Какова временная сложность задачи «Счастливое число»?

На первом шаге считываются O(log n) цифры числа n. Все последующие значения меньше 1000, а последовательность повторяется не более чем через 20 чисел, поэтому общее время работы составляет O(log n). Вариант с хеш-множеством хранит посещённые числа; вариант Флойда использует O(1) памяти.

Почему все несчастливые числа в итоге приходят к 4?

Проверка всех чисел меньше 1000 показывает, что существует ровно один цикл, не содержащий 1: 4, 16, 37, 58, 89, 145, 42, 20 и снова 4. Поскольку при любом начальном значении число становится меньше 1000, каждое несчастливое число попадает в этот цикл. Решение может остановиться, как только встретит 4, но для этого нужно знать факт, который пришлось бы обосновывать на собеседовании; множество и метод Флойда не требуют таких знаний.

Как связано счастливое число с циклом в связном списке?

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

Python

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

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

Случай 1

Случай 2

Случай 3

Ввод

n = 7

Ожидается

true