# 287. Find the Duplicate Number

## Problem Statement

<br>

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*.

You must solve the problem **without** modifying the array `nums` and uses only constant extra space.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,3,4,2,2]
</strong><strong>Output: 2
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [3,1,3,4,2]
</strong><strong>Output: 3
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= n <= 105`
* `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.

## Intuition

```
https://leetcode.com/problems/find-the-duplicate-number/solutions/1892872/c-6-approaches-interview-question/

Follow this link for explanations
```

### Links

<https://leetcode.com/problems/find-the-duplicate-number/description/>

### Video Links

### Approach 1:

```
NlogN using sort
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i=1; i<nums.size(); i++){
            if(nums[i] == nums[i-1])
                return nums[i];
        }

        return -1;
    }
};
```

{% endcode %}

### Approach 2:

```
N Time + N Space using map
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        unordered_map<int, int> mp;
        for(auto &it: nums){
            if(mp.find(it) == mp.end())
                mp[it]++;
            else
                return it;
        } 

        return -1;
    }
};
```

{% endcode %}

### Approach 3:

```
NlogN Time + 1 Space using BS
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1, high = nums.size() - 1, cnt;
        
        while(low <=  high)
        {
            int mid = low + (high - low) / 2;
            cnt = 0;
            // cnt number less than equal to mid
            for(int n : nums)
            {
                if(n <= mid)
                    ++cnt;
            }
            // binary search on left
            if(cnt <= mid)
                low = mid + 1;
            else
            // binary search on right
                high = mid - 1;
            
        }
        return low;
    }
};
```

{% endcode %}

### Approach 4:

```
Important method , N Time + 1 Space 

Marking the index 

Basically we treat elements as index and 
LEt say we get 4, we make nums[4] as -nums[4]

But duplicate element will cause double changes, will get caught
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        
        for(int i = 0; i < n; ++i){
            int idx = abs(nums[i]);
            
            if(nums[idx] < 0)
                return idx;
            
            nums[idx] = -nums[idx];
        }
        
        return n;
    }
};
```

{% endcode %}

### Similar Problems

###