Floyd cycle detection algorithm for linera time and linear space
inline int FloydCycleFind(int x0){ x0%=m; if(!k) return x0; int hare = f(f(x0)), tortoise = f(x0); while(tortoise != hare){ hare = f(f(hare)); tortoise = f(tortoise); } int mu = 0; hare = x0; while(tortoise!=hare){ hare = f(hare); tortoise = f(tortoise); mu++; if(mu == k) return hare; } k-=mu; int lambda = 1; hare=f(tortoise); while(hare!=tortoise) hare=f(hare), lambda++; k%=lambda; while(k) tortoise = f(tortoise), k--; return tortoise; }
https://toph.co/p/not-my-fault
Comments
Post a Comment