:orphan:

Single Number
=============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/single-number/

Given a **non-empty** array of integers ``nums``, every element appears
*twice* except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use
only constant extra space.



**Example 1:**

::

   Input: nums = [2,2,1]
   Output: 1

**Example 2:**

::

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

**Example 3:**

::

   Input: nums = [1]
   Output: 1



**Constraints:**

- ``1 <= nums.length <= 3 * 10``\ :sup:`4`
- ``-3 * 10``\ :sup:`4`\ ``<= nums[i] <= 3 * 10``\ :sup:`4`
- Each element in the array appears twice except for one element which
  appears only once.

.. highlight:: python

Pattern
-------
Bit Manipulation

Approaches
----------

.. tab-set::

    .. tab-item:: XOR

        **Code**

        .. literalinclude:: ../problems/medium/single-number/single_number__xor.py
            :language: python
            :lines: 12-

        **Test**

        >>> from single_number__xor import singleNumber
        >>> singleNumber([2, 2, 1])
        1
        >>> singleNumber([4, 1, 2, 1, 2])
        4
        >>> singleNumber([1])
        1

        .. autofunction:: single_number__xor.singleNumber