Войти Регистрация
Алгоритмы

153. Где замыкается цепочка автопереводов

Средняя

Счета пронумерованы от 0 до n − 1. Со счёта i настроен автоперевод остатка на счёт nxt[i] (может быть и на себя).

Деньги со счёта 0 идут по цепочке 0 → nxt[0] → nxt[nxt[0]] → …. Счетов конечное число, поэтому цепочка обязательно зациклится.

Верните [вход, длина]: первый счёт цепочки, который лежит на цикле, и число счетов в цикле. Решите без дополнительной памяти, пропорциональной n.

В работе: Антифрод-проверка в Альфа-Банке: автопереводы клиента замкнулись в кольцо, и деньги бесконечно ходят между счетами с комиссией.

Пример 1

Ввод
nxt = [1, 2, 3, 4, 2]
Вывод
[2, 3]

0 → 1 → 2 → 3 → 4 → 2: цикл 2, 3, 4 длины 3.

Пример 2

Ввод
nxt = [0]
Вывод
[0, 1]

Счёт переводит сам себе: цикл длины 1 на счёте 0.

Ограничения

  • 1 ≤ n ≤ 10⁵
  • 0 ≤ nxt[i] < n
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def chain_loop(nxt):
Цикл ФлойдаДва указателяФункциональный графцельO(n)

Источник: наша задача на данных Альфа-Банка. Условие пересказано своими словами.