:orphan:

Find the Duplicate Number
=========================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/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*.

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

 

**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 = [3,3,3,3,3]
   Output: 3

 

**Constraints:**

- ``1 <= n <= 10``\ :sup:```5```
- ``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 in linear runtime complexity?

.. highlight:: python

Pattern
-------
Array, Two Pointers, Binary Search, Bit Manipulation

Approaches
----------

.. tab-set::

    .. tab-item:: Negation Marking

        **Code**

        .. literalinclude:: ../problems/medium/find-the-duplicate-number/find_the_duplicate_number__negation_marking.py
            :language: python
            :lines: 12-

        **Test**

        >>> from find_the_duplicate_number__negation_marking import findDuplicate
        >>> findDuplicate([1, 3, 4, 2, 2])
        2
        >>> findDuplicate([3, 1, 3, 4, 2])
        3
        >>> findDuplicate([3, 3, 3, 3, 3])
        3

        .. autofunction:: find_the_duplicate_number__negation_marking.findDuplicate