{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

268. Missing Number

\n", "
\n", "\n", "\n", "

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

\n", "\n", "

 

\n", "

Example 1:

\n", "\n", "
Input: nums = [3,0,1]\n",
    "Output: 2\n",
    "Explanation: 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",
    "
\n", "\n", "

Example 2:

\n", "\n", "
Input: nums = [0,1]\n",
    "Output: 2\n",
    "Explanation: 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",
    "
\n", "\n", "

Example 3:

\n", "\n", "
Input: nums = [9,6,4,2,3,5,7,0,1]\n",
    "Output: 8\n",
    "Explanation: 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",
    "
\n", "\n", "

Example 4:

\n", "\n", "
Input: nums = [0]\n",
    "Output: 1\n",
    "Explanation: 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",
    "
\n", "\n", "

 

\n", "

Constraints:

\n", "\n", "\n", "
\n", "\n", "\n", "

 

\n", "Source \n", "
\n", "\n", "

Code

" ] }, { "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": [ "

Check

" ] }, { "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": [ "
\n", "

Follow up:

\n", "

Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

\n", "\n", "

Code

" ] }, { "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": [ "

Check

" ] }, { "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 }