# problem287

package
Version: v1.6.5 Latest Latest

Go to latest
Published: Mar 23, 2021 License: MIT

### 287. Find the Duplicate Number (Medium)

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 * 104`
• `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.

• 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(n2)`?

[Array] [Two Pointers] [Binary Search]

#### Similar Questions

1. First Missing Positive (Hard)
2. Single Number (Easy)
3. Linked List Cycle II (Medium)
4. Missing Number (Easy)
5. Set Mismatch (Easy)

## Documentation ¶

There is no documentation for this package.