59. 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 (but can repeated more than once), return this duplicate number.

You must not modify the array (assume it is read-only), and you must use only constant extra space.

Your algorithm should run in less than O(n²) time.

Example 1:

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

Output: 2

Example 2:

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

Output: 3

Now Your Turn!

Pick the correct output for the given input

Input: nums = [1,1]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • Only one duplicate number, but it can be repeated more than once

Fun Facts

0
class Solution {
public:
int findDuplicate(vector<int>& nums) {
// Your code goes here
}
};
 
Test Case

Input:

Nums