title: Understanding why Floyd's tortoise and hare algorithm works when applied to an array of integers
body: <p>I was trying to solve this leetcode problem <a href="https://leetcode.com/problems/find-the-duplicate-number/" rel="noreferrer">https://leetcode.com/problems/find-the-duplicate-number/</a> using my own implementation of the tortoise and hare algorithm which resulted in an infinite loop when given the following array of integers:</p>
  <p>[3,1,3,4,2]</p>
  <p>Only after tracing through my algorithm was I able to see that the slow and fast runners never take on the two duplicate values at the same time. Here is my algorithm in pseudocode:</p>
  <pre><code>initialize fast and slow runners to 0
  
  while(true)
  
     move fast runner two indices forward
     move slow runner one index forward
  
     if arr[fast] == arr[slow] and fast != slow
        return arr[fast] // this is the duplicate
  </code></pre>
  <p>Now, I'm sure someone who is skilled in discrete mathematics would have been able to intuitively know that this approach would not have lead to the correct solution without first having to trace through an example like I had to do.</p>
  <p>What inferences or observations could I have made that would have lead me to see that this algorithm was not going to work? I'd like to know how one could intuitively identity a flaw in this logic through a series of logical statements. In other words, what's the explanation for why the two runners will never find the duplicates in this example? I feel like it may have something to do with counting, but I do not have a very strong background in discrete.</p>
  <p>And to clarify, I have looked at the correct implementation so I do know what the correct way to solve it is. I just thought that this way would have worked too similar to applying it to linked lists, where you'd move the fast runner two nodes up and the slow runner one node up. Thank you for your help.</p>