#!/usr/bin/env python
# coding: utf-8

# <h1>268. Missing Number</h1>
# <hr>
# 
# <!--Copy Paste Leetcode statement between-->
# <div><p>Given an array <code>nums</code> containing <code>n</code> distinct numbers in the range <code>[0, n]</code>, return <em>the only number in the range that is missing from the array.</em></p>
# 
# <p>&nbsp;</p>
# <p><strong>Example 1:</strong></p>
# 
# <pre><strong>Input:</strong> nums = [3,0,1]
# <strong>Output:</strong> 2
# <b>Explanation</b><strong>:</strong> n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
# </pre>
# 
# <p><strong>Example 2:</strong></p>
# 
# <pre><strong>Input:</strong> nums = [0,1]
# <strong>Output:</strong> 2
# <b>Explanation</b><strong>:</strong> n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
# </pre>
# 
# <p><strong>Example 3:</strong></p>
# 
# <pre><strong>Input:</strong> nums = [9,6,4,2,3,5,7,0,1]
# <strong>Output:</strong> 8
# <b>Explanation</b><strong>:</strong> n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
# </pre>
# 
# <p><strong>Example 4:</strong></p>
# 
# <pre><strong>Input:</strong> nums = [0]
# <strong>Output:</strong> 1
# <b>Explanation</b><strong>:</strong> n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.
# </pre>
# 
# <p>&nbsp;</p>
# <p><strong>Constraints:</strong></p>
# 
# <ul>
# 	<li><code>n == nums.length</code></li>
# 	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
# 	<li><code>0 &lt;= nums[i] &lt;= n</code></li>
# 	<li>All the numbers of <code>nums</code> are <strong>unique</strong>.</li>
# </ul>
# </div>
# <!--Copy Paste Leetcode statement between-->
# 
# <p>&nbsp;</p>
# <a href="https://leetcode.com/problems/missing-number/">Source</a> 
# <hr>
# 
# <h4>Code</h4>

# In[1]:


def missing_number(nums):
    """Using a Hash Table.
    Time complexity: O(n)
    Space Complexity: O(n)
    """
    my_set = set(nums)
    for i in range(len(nums)+1):
        if number not in my_set:
            return number


# In[2]:


def missing_number(nums):
    """Using sort
    Time complexity: O(nlogn)
    Space Complexity: O(1)
    """
    nums.sort()
    for i, n in enumerate(nums):
        if n != i:
            return i
    return len(nums)


# <h4>Check</h4>

# In[5]:


nums = [3,0,1]
missing_number(nums)


# In[6]:


nums = [0,1]
missing_number(nums)


# In[7]:


nums = [1]
missing_number(nums)


# In[8]:


nums = [9,6,4,2,3,5,7,0,1]
missing_number(nums)


# <hr>
# <h4>Follow up:</h4>
# <p>Could you implement a solution using only <code>O(1)</code> extra space complexity and <code>O(n)</code> runtime complexity?</p>
# 
# <h4>Code</h4>

# In[3]:


def missing_number(nums):
    """Using XOR which is its own inverse (0^x = x and x^x = 0)
    Time complexity: O(n)
    Space Complexity: O(1)
    """
    missing = len(nums)
    for i, a in enumerate(nums):
        missing = missing ^ i ^ a  # in the end, we have twice 0 ^ 1 ^ 2 ^ ... ^ n ^ n+1  but for missing number
        # i=0:     n+1 ^ 0 ^ a(0)
        # i=1:     n+1 ^ 0 ^ a(0) ^ 1 ^ a(1)
        # i=2:     n+1 ^ 0 ^ a(0) ^ 1 ^ a(1) ^ 2 ^ a(2)
        # ...
        # i= n-1:  n+1 ^ 0 ^ 1 ^ 2 ^ ... ^ n-1 ^ a(0) ^ a(1) ^ a(2) ^ ... ^ a(n-1)
        # i= n:    n+1 ^ 0 ^ 1 ^ 2 ^ ... ^ n-1 ^ n ^ a(0) ^ a(1) ^ a(2) ^ ... ^ a(n-1) ^ a(n)
    return missing


# In[4]:


def missing_number(nums):
    """Using Gauss formula: sum(0..n) = n(n+1)/2
    Time complexity: O(n)
    Space Complexity: O(1)
    """
    expected_sum = len(nums)*(len(nums)+1)//2
    actual_sum = sum(nums)
    return expected_sum - actual_sum


# <h4>Check</h4>

# In[9]:


nums = [3,0,1]
missing_number(nums)


# In[10]:


nums = [0,1]
missing_number(nums)


# In[11]:


nums = [1]
missing_number(nums)


# In[12]:


nums = [9,6,4,2,3,5,7,0,1]
missing_number(nums)