linked lists

Consider the following problem: Given an array of integers nums containing $n + 1$ integers where each integer is in the range $[1, \dots, n]$ inclusive, where there is only one repeated number in nums return this repeated number.

We propose that the following algorithm does this:

# Note this is in Python
def find_duplicate(nums: List[int]) -> int:
    # loop 1
    slow1 = 0
    fast = 0
    while True:
        slow1 = nums[slow1]
        fast = nums[nums[fast]]
        if slow1 == fast:
            break

    # loop 2
    slow2 = 0
    while slow1 != slow2:
        slow1 = nums[slow1]
        slow2 = nums[slow2]
    return slow1

Repeated Element in Tuple

Given a

n

-tuple

A

, where

n \geq 2

, a repeated element

x

A

is an element such that

A_{i} = A_{j} = x

, where

i \neq j

Index Array

An index array is an array whose values are valid indices to itself

Index Array Graph

Given an index array

A

then it's induced graph

G

is a directed graph whose vertices are the elements of

A

, it's edges are obtained as follows,

Set $g_{0} = 0$ and for any $i \in N_{0}$ let $g_{i + 1} = A [g_{i}]$
The graph has edges: $(g_{i}, g_{i + 1})$

We also define the sequnce

g : = (g_{0}, g_{1}, g_{2}, \dots)

as its movement sequence.

The index array graph can be constructed by extending the behavior of $s l o w 1$ in the first while loop.

Meet Value

Given the index array graph for an index array

A

, we define the meet value as

g_{j}

where

j \in N_{0}

is the smallest index such that

(g_{0}, g_{1}, g_{2}, \dots g_{j})

has a repeated element.

All Input Arrays have a Meet Value

Suppose that

A

is an array of

n + 1

integers such that

a_{i} \in [1, \dots, n]

, such that there is only one repeated number, then

A

has a meet value.

From the definition of the index array graph, consider it's movement sequence

g : = (g_{0}, g_{1}, g_{2}, \dots)

and it's set define as

X : = {g_{i} : i \in N_{0}}

, by definition of

A

the movement sequence contains at most

n

unique numbers and so we see that

| X | \leq n

, and thus it is finite, this means that there is some duplicated element in the movement sequence, suppose there is not, then each element is unique, and so

X

would be infinite, which is a contradiction, thus there is some duplicated element in the movement sequence, and so a meet value exists.

All Index Array Graphs have A Cycle Continuing Forever

As per title.

Since we know that all inputs arrays have a meet value then it's movement sequence is of the form

g_{0}, \dots g_{i}, g_{i + 1} \dots g_{i + k}, g_{i}, g_{i + 1}, \dots g_{i + k}, \dots

, where

g_{i}

is the meet value, and there are

k

other elements encountered before we get to the meet value. It must continue forever because after

g_{i}

is encountered for the second element, then the next element is defined as

A [g_{i}]

which is the same as the definition of

g_{i + 1}

and so on until

g_{i}

is reached again, therefore it continues cycling forever.

Termination of the First While Loop

The first while loop terminates and

s l o w 1 = f a s t

, moreover it takes

x + y

iterations to terminate where

x

is the index of the meet value, and

y \in {0, \dots k}

where

k + 1

is the length of the cycle that is guaranteed to exist

Let ${s l o w 1}_{k}$ be the value of $s l o w 1$ at the end of the $k$ -th iteration of the while loop. Observe that $g_{k} = {s l o w 1}_{t}$ , this holds true for $k = 0$ as well where we have $g_{0} = 0 = {s l o w 1}_{0}$ , note that the equality holds true as each iteration of the while loop directly pertains the recursive definition of $g_{i + 1}$ , moreover note that ${f a s t}_{k} = g_{2 k}$ which can be verified in a similar manner. Note that this means that $f a s t$ 's movement sequence is a subsequence of $s l o w 1$ 's denote this subsequence $s : = (s_{0}, s_{1}, s_{2}, \dots)$ where $s_{i} = g_{2 i}$ then we know that ${f a s t}_{k} = s_{k}$ .

Let $G$ be the index array graph of $A$ , we know that it has a cycle that it gets stuck in forever, and suppose that the elements of the cycle are given by $C = (c_{0}, c_{1}, \dots, c_{k})$ , where $c_{0}$ is the meet value.

Consider the smallest index $x$ where $g_{x}$ and $s_{x}$ are both in $C$ for the first time. Since the start of the cycle is the meet value, then we know that $g_{x} = c_{0}$ whereas $s_{x} = c_{i}$ where $i \in N_{0}$

Since $C$ is a cycle of length $k + 1$ and $f a s t$ traverses $C$ at twice the speed of $s l o w 1$ , (which is to say that $g_{x + y} = c_{(0 + y) % k + 1}$ and $s_{x + y} = c_{(y + 2 y) % k + 1}$ ) in tandem with the fact that all elements in the cycle are distinct and thus we know that $c_{a} = c_{b}$ if and only if $a % (k + 1) = b % (k + 1)$ , we conclude that $g_{x + y} = s_{x + y}$ when $y \equiv i + 2 y (\mod k + 1)$ , where $y$ is the $y$ -th iteration after $s l o w 1$ and $f a s t$ are both in $C$ for the first time.

Rearranging shows $y \equiv - i (\mod k + 1)$ , if $i = 0$ , then this is satisfied by $y = 0$ which means that when both $s l o w 1 = c_{0} = f a s t$ when they enter the cycle for the first time. On the other hand if $i > 0$ then $y = k + 1 - i$ satisfies the equation. Note that there are infinitely other non-negative solutions, but these two solutions are the smallest ones, thus the while loop will encounter these first before any larger ones and terminate, thus $y \in {0, \dots, k}$ .

Termination of the Seond while loop and the Value of

s l o w 1

is the Meet Value

The second while loop terminates, and after termination,

s l o w 1 = g_{x}

, where

g_{x}

is the meet value of the input array

A

Assume the first while loop terminates after

t

iterations.

Let

G

be the index array graph of

A

. By Corollary: All Index Array Graphs have A Cycle Continuing Forever,

G

has a cycle

C = (c_{0}, c_{1}, \dots, c_{k})

. Without a loss of generality, assume

c_{0} = g_{x}

. Let

g = (g_{0}, g_{1}, g_{2}, \dots)

be the movement sequence of

G

. Now, let

y \in ℕ_{0}

be the smallest number such that

g_{x + y} = {s l o w 1}_{t}

at iteration

t

(i.e., termination) of the first while loop. Finally, let

z \in ℕ_{0}

be the smallest number such that

g_{x + y + z} = c_{0}

. It is worth noting that

y + z = k + 1

, thus

y + z

is the length of

C

.

We know that the first while loop terminates at iteration

t = x + y

. Since

{f a s t}_{t} = {s l o w 1}_{2 t}

at iteration

t

, we know

{f a s t}_{x + y} = {s l o w 1}_{2 (x + y)} = g_{2 (x + y)}

. Therefore, we can say that upon termination of the first while loop,

f a s t

has travelled

2 (x + y)

nodes into

g

.

For an alternative but equivalent statement of this fact, assume

f a s t

completes

n

full cycles around

C

by iteration

t

. Then,

{f a s t}_{t} = g_{x + n (k + 1) + y} = g_{x + n (y + z) + y}

. Hence, we can also say that upon termination of the first while loop,

f a s t

has travelled

x + n (y + z) + y

nodes into

g

.

These two equivalent statements brings us to the following result.

\begin{matrix} 2 (x + y) & = x + n (y + z) + y \\ 2 x + 2 y & = x + (n + 1) y + n z \\ x & = (n - 1) y + n z \\ x & = (n - 1) (y + z) + z \\ x & = (n - 1) (k + 1) + z \end{matrix}

Therefore, travelling

x

nodes into

g

is equivalent to completing

n - 1

complete cycles around

C

and travelling another

z

nodes.

Now consider the second while loop. On iteration 0,

s l o w 1 = g_{x + y}

and

s l o w 2 = g_{0}

. Now consider iteration

x

. On iteration

x

s l o w 1 = g_{x + y + x}

\begin{matrix} g_{x + y + x} & = g_{x + y + (n - 1) (k + 1) + z} \\ = g_{x + (y + z) + (n - 1) (k + 1)} \\ = g_{x + (k + 1) + (n - 1) (k + 1)} \\ = g_{x + n (k + 1)} \end{matrix}

Given

g_{x}

is in

C

g_{x + y + x}

is just

n

complete cycles around

C

from

g_{x}

. Therefore,

g_{x + y + x} = g_{x}

. On iteration

x

, we also trivially know

s l o w 2 = g_{x}

. Hence,

s l o w 1 = s l o w 2

so the second while loop terminates, and upon termination,

s l o w 1 = g_{x}

The Meet Value is the Duplicated Value

Let

A

an an array which satisfies the specification of the algorithm where

d

is its duplicated element and

m \in A

be the meet value, then

m = d

By definition of the meet value, it is encountered twice in the movement sequence $g : = (g_{0}, g_{1}, g_{2}, \dots)$ on it's first encounter, we have some index $i$ such that $g_{i} = m$ by the definition of the movement sequence this means that $A [g_{i - 1}] = m$ so that $g_{i - 1}$ is the index of $m$ in $A$

On the second encounter of $m$ in the movement sequence we have some $j$ where $(j > i)$ such that $g_{j} = m$ so also that $A [g_{j - 1}] = m$ . Now note that with respect to the movement sequence, we have the following subsequence $g_{i - 1}, m, \dots, g_{j - 1}, m$ , if $g_{i - 1} = g_{j - 1}$ then we get contradiction because by the definition of the meet value $g_{j} = m$ it's assumed that $j$ was the smallest value such that $(g_{0}, \dots, g_{m})$ has a duplicated value, but under the assumption that $g_{i - 1} = g_{j - 1}$ then $j - 1$ would be a smaller value such that $(g_{0}, \dots, g_{j - 1})$ has a repeated value, therefore we must have that $g_{i - 1} \neq g_{j - 1}$ .

Recall that $A [g_{i - 1}] = A [g_{j - 1}] = m$ therefore $m$ is duplicated in $A$ . Since $A$ contains exactly one duplicated element, then we must conclude that $d = m$ .

f i n d_d u p l i c a t e

is Correct

Given an

(n + 1)

-tuple consisting of elements in the range

[1, n]

with exactly one repeated element, the algorithm above returns that element.

We know that the first while loop terminates. We know that the second while loop terminates (therefore the entire program terminates) and the value of

s l o w 1

is the meet value. We also know that the meet value is the duplicated value therefore since the algorithm returns

s l o w 1

then it returns the duplicated value.

🏗️ ΘρϵηΠατπ🚧 (under construction)

🏗️ $Θ ρ ϵ η Π α τ π$ 🚧 (under construction)