:orphan:

Single Number Ii
================

.. highlight:: none

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

Given an integer array ``nums`` where every element appears **three
times** except for one, which appears **exactly once**. *Find the single
element and return it*.

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

 

**Example 1:**

::

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

**Example 2:**

::

   Input: nums = [0,1,0,1,0,1,99]
   Output: 99

 

**Constraints:**

- ``1 <= nums.length <= 3 * 10``\ :sup:```4```
- ``-2``\ :sup:```31```\ ``<= nums[i] <= 2``\ :sup:```31```\ ``- 1``
- Each element in ``nums`` appears exactly **three times** except for
  one element which appears **once**.

.. highlight:: python

Pattern
-------
Array, Bit Manipulation

Solution
--------
For each bit position, we sum the bits in that position across ``nums``. For
the integers in ``nums`` that appear 3 times, the number of 1s in each position
will be a multiple of 3. For each position, we can extract the bit value of
the integer :math:`x` that appears once by modding the sum by 3. If :math:`x`
is negative, then the bit values will be in 2's complement form. We can convert
unsigned integers to 2's complement by subtracting :math:`2^{32}`.

Code
----

.. literalinclude:: ../problems/medium/single-number-ii/single_number_ii__approach_1.py
    :language: python
    :lines: 9-

Test
----
>>> from single_number_ii__approach_1 import singleNumber
>>> singleNumber([2, 2, 3, 2])
3
>>> singleNumber([0, 1, 0, 1, 0, 1, 99])
99

Complexity
----------
| :math:`n` is the length of the input array
| Time: :math:`O(n)` — single pass through the array
| Auxiliary Space: :math:`O(1)` — fixed 32-bit array to store sum

.. autofunction:: single_number_ii__approach_1.singleNumber

.. autofunction:: single_number_ii__approach_1.getBit