> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/binary-search/bs-on-1d-array/287.-find-the-duplicate-number.md).

# 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

###


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/binary-search/bs-on-1d-array/287.-find-the-duplicate-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.