Reference: LeetCode

Difficulty: Medium

## Problem

Given an array nums containing

`n + 1`

integers where each integer is between`1`

and`n`

(inclusive), prove that at least one duplicate number must exist. Assume that there is`only one duplicate number`

, find the duplicate one.

**Example:**

1 | Input: [1,3,4,2,2] |

**Note:**

- You must not modify the array (assume the array is read only).
- You must use only constant, $O(1)$ extra space.
- Your runtime complexity should be less than $O(n^2)$.
- There is only one duplicate number in the array, but it could be
`repeated more than once`

.

## Analysis

### Hash Set

**Note:** It uses extra space.

1 | public int findDuplicate(int[] nums) { |

**Time:** $O(N)$**Space:** $O(N)$

### Sorting

If the numbers are sorted, then any duplicate numbers will be adjacent in the sorted array.

**Note:** It modifies the original array.

1 | public int findDuplicate(int[] nums) { |

**Time:** $O(N\log{N})$**Space:** $O(1)$

### Reduce to Cycle Detection

Reference: Solution Section

We can interpret `nums`

such that for each pair of index `i`

and value `val`

. Then the problem can be reduced to cycle detection. The entry point is the corresponding duplicate number.

1 | Example: [1, 3, 4, 2, 2] |

The problem can be reduced to as follows:

1 | 0 --> 1 --> 3 --> 2 --> 4 |

We assume that the cycle must exists.

1 | public int findDuplicate(int[] nums) { |

**Time:** $O(N)$**Space:** $O(1)$