## 287. Find the Duplicate Number

Given an array of integers `nums`

containing `n + 1`

integers where each integer is in the range `[1, n]`

inclusive.

There is only **one repeated number** in `nums`

, return *this repeated number*.

**Example 1:**

Input:nums = [1,3,4,2,2]Output:2

**Example 2:**

Input:nums = [3,1,3,4,2]Output:3

**Example 3:**

Input:nums = [1,1]Output:1

**Example 4:**

Input:nums = [1,1,2]Output:1

**Constraints:**

`2 <= n <= 3 * 10`

^{4}`nums.length == n + 1`

`1 <= nums[i] <= n`

- All the integers in
`nums`

appear only**once**except for**precisely one integer**which appears**two or more**times.

**Follow up:**

- How can we prove that at least one duplicate number must exist in
`nums`

? - Can you solve the problem
**without**modifying the array`nums`

? - Can you solve the problem using only constant,
`O(1)`

extra space? - Can you solve the problem with runtime complexity less than
`O(n`

?^{2})

## Rust Solution

```
struct Solution;
impl Solution {
fn find_duplicate(nums: Vec<i32>) -> i32 {
let n = (nums.len() - 1) as i32;
let mut low = 1;
let mut high = n;
while low < high {
let mid = low + (high - low) / 2;
let mut count = 0;
for &x in &nums {
if x <= mid {
count += 1;
}
}
if count <= mid {
low = mid + 1;
} else {
high = mid;
}
}
low
}
}
#[test]
fn test() {
let nums = vec![1, 3, 4, 2, 2];
let res = 2;
assert_eq!(Solution::find_duplicate(nums), res);
let nums = vec![3, 1, 3, 4, 2];
let res = 3;
assert_eq!(Solution::find_duplicate(nums), res);
}
```

Having problems with this solution? Click here to submit an issue on github.