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