Happy Number

Лёгкая№202цикл

Берём положительное число и снова и снова заменяем его суммой квадратов его цифр. Число счастливое, если так получится 1, и несчастливое, если числа ходят по кругу и до 1 не доходят. Верни, счастливое ли n. Наш пример: n = 7, путь 7 → 49 → 97 → 130 → 10 → 1 — ответ true.

202 Happy NumberРазбор · 1×

Пример: n = 7: каждое число ведёт к сумме квадратов своих цифр, 7 → 49 → 97 → 130 → 10 → 1 → 1.

n74997130101slow
slowfastместо встречи

slow = n = 7

01/19
сначала · назад · пуск · шаг
Скорость
1function isHappy(n):
2 slow = n
3 fast = next(n) // the sum of squared digits
4 while slow != fast:
5 slow = next(slow)
6 fast = next(next(fast))
7 return slow == 1
состояние
slow
7
fast
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. У каждого числа ровно одно следующее, поэтому числа образуют связный список, и расти бесконечно он не может: число из d цифр ведёт не дальше 81·d, а это меньше самого числа, если в нём от четырёх цифр. Значит, список скоро опускается ниже тысячи, там и остаётся и рано или поздно возвращается к уже встреченному числу.
  2. Значит, любой такой список заканчивается петлёй, и 1 — тоже петля: next(1) = 1. Slow и fast встречаются на этой петле, какой бы она ни была, и ответ — встретились ли они на 1.
  3. Множество увиденных чисел не нужно: петлю находят два указателя. Все несчастливые числа приходят в одну и ту же петлю: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4.

Сложность

Время O(log n): первый шаг читает цифры n, их около log n, и даёт не больше 81 на цифру, меньше тысячи для любого 32-битного n; дальше и путь, и петля короткие. Память O(1): два числа.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.