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

Popular posts from this blog

C++ STL practice problem link

Binary Index Tree(BIT)

Combinatorics