{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<h1>268. Missing Number</h1>\n",
"<hr>\n",
"\n",
"<!--Copy Paste Leetcode statement between-->\n",
"<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>\n",
"\n",
"<p> </p>\n",
"<p><strong>Example 1:</strong></p>\n",
"\n",
"<pre><strong>Input:</strong> nums = [3,0,1]\n",
"<strong>Output:</strong> 2\n",
"<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.\n",
"</pre>\n",
"\n",
"<p><strong>Example 2:</strong></p>\n",
"\n",
"<pre><strong>Input:</strong> nums = [0,1]\n",
"<strong>Output:</strong> 2\n",
"<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.\n",
"</pre>\n",
"\n",
"<p><strong>Example 3:</strong></p>\n",
"\n",
"<pre><strong>Input:</strong> nums = [9,6,4,2,3,5,7,0,1]\n",
"<strong>Output:</strong> 8\n",
"<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.\n",
"</pre>\n",
"\n",
"<p><strong>Example 4:</strong></p>\n",
"\n",
"<pre><strong>Input:</strong> nums = [0]\n",
"<strong>Output:</strong> 1\n",
"<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.\n",
"</pre>\n",
"\n",
"<p> </p>\n",
"<p><strong>Constraints:</strong></p>\n",
"\n",
"<ul>\n",
"\t<li><code>n == nums.length</code></li>\n",
"\t<li><code>1 <= n <= 10<sup>4</sup></code></li>\n",
"\t<li><code>0 <= nums[i] <= n</code></li>\n",
"\t<li>All the numbers of <code>nums</code> are <strong>unique</strong>.</li>\n",
"</ul>\n",
"</div>\n",
"<!--Copy Paste Leetcode statement between-->\n",
"\n",
"<p> </p>\n",
"<a href=\"https://leetcode.com/problems/missing-number/\">Source</a> \n",
"<hr>\n",
"\n",
"<h4>Code</h4>"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"def missing_number(nums):\n",
" \"\"\"Using a Hash Table.\n",
" Time complexity: O(n)\n",
" Space Complexity: O(n)\n",
" \"\"\"\n",
" my_set = set(nums)\n",
" for i in range(len(nums)+1):\n",
" if number not in my_set:\n",
" return number"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"def missing_number(nums):\n",
" \"\"\"Using sort\n",
" Time complexity: O(nlogn)\n",
" Space Complexity: O(1)\n",
" \"\"\"\n",
" nums.sort()\n",
" for i, n in enumerate(nums):\n",
" if n != i:\n",
" return i\n",
" return len(nums)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<h4>Check</h4>"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nums = [3,0,1]\n",
"missing_number(nums)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nums = [0,1]\n",
"missing_number(nums)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nums = [1]\n",
"missing_number(nums)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"8"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nums = [9,6,4,2,3,5,7,0,1]\n",
"missing_number(nums)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<hr>\n",
"<h4>Follow up:</h4>\n",
"<p>Could you implement a solution using only <code>O(1)</code> extra space complexity and <code>O(n)</code> runtime complexity?</p>\n",
"\n",
"<h4>Code</h4>"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"def missing_number(nums):\n",
" \"\"\"Using XOR which is its own inverse (0^x = x and x^x = 0)\n",
" Time complexity: O(n)\n",
" Space Complexity: O(1)\n",
" \"\"\"\n",
" missing = len(nums)\n",
" for i, a in enumerate(nums):\n",
" missing = missing ^ i ^ a # in the end, we have twice 0 ^ 1 ^ 2 ^ ... ^ n ^ n+1 but for missing number\n",
" # i=0: n+1 ^ 0 ^ a(0)\n",
" # i=1: n+1 ^ 0 ^ a(0) ^ 1 ^ a(1)\n",
" # i=2: n+1 ^ 0 ^ a(0) ^ 1 ^ a(1) ^ 2 ^ a(2)\n",
" # ...\n",
" # i= n-1: n+1 ^ 0 ^ 1 ^ 2 ^ ... ^ n-1 ^ a(0) ^ a(1) ^ a(2) ^ ... ^ a(n-1)\n",
" # i= n: n+1 ^ 0 ^ 1 ^ 2 ^ ... ^ n-1 ^ n ^ a(0) ^ a(1) ^ a(2) ^ ... ^ a(n-1) ^ a(n)\n",
" return missing"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"def missing_number(nums):\n",
" \"\"\"Using Gauss formula: sum(0..n) = n(n+1)/2\n",
" Time complexity: O(n)\n",
" Space Complexity: O(1)\n",
" \"\"\"\n",
" expected_sum = len(nums)*(len(nums)+1)//2\n",
" actual_sum = sum(nums)\n",
" return expected_sum - actual_sum"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<h4>Check</h4>"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nums = [3,0,1]\n",
"missing_number(nums)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nums = [0,1]\n",
"missing_number(nums)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nums = [1]\n",
"missing_number(nums)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"8"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nums = [9,6,4,2,3,5,7,0,1]\n",
"missing_number(nums)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.2"
}
},
"nbformat": 4,
"nbformat_minor": 1
}