+++ title = "Cycle Finding Algorithms" date = 2023-12-19T00:27:00+08:00 tags = ["cycle-finding"] categories = ["Data-Structure-and-Algorithm"] draft = false image = "/images/icons/TortoiseHare.jpg" libraries = ["mathjax"] description = "this is a description" +++
{{< figure src="/images/posts/cycle-finding/tortoise-and-hare.svg" caption="<span class="figure-number">Figure 1: tortoise and hare" >}}
hare and tortoise both starts from point Start, at speed of \(2\) and \(1\) respectively. They'll meet at some point in the cycle.
when they meet, hare traveled \(S_2 - S_{1}\) more points than tortoise. We have: (\(\lambda\) is the cycle length)
\[ S_{2} - S_{1} = 0 = S_{1} = x + m \pmod{\lambda} \]
after they meet, one starts over from Start point, the other starts from Meet point, at speed of \(1\), they'll meet again at Cycle Start point. because:
\[ x = x + m + x \pmod{\lambda} \]