{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 1:\n",
    "Given an integer array, find the missing number:\n",
    "\n",
    "- Input = [1, 2, 3, 4, 6, 7]\n",
    "- Output = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def missingNumber(arr): \n",
    "    n = len(arr) + 1 #Since a number is missing, we need to add an extra element.\n",
    "    theoritical_sum = (n * (n + 1))/2\n",
    "    actual_sum = sum(arr)\n",
    "    return int(theoritical_sum - actual_sum)\n",
    "\n",
    "missingNumber([1, 2, 3, 4, 6, 7])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 2:\n",
    "Given an integer array, find the pairs whose sum is equal to a given number. \n",
    "- Input: [1, 2, 3, 4, 5] target_sum = 7\n",
    "- Output: (3, 4), (2, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(5, 2), (2, 5), (3, 4), (4, 3)]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Method 1\n",
    "def findSum(arr, target): # Time Complexity: O(n^2)\n",
    "    results = []\n",
    "    for i in arr:\n",
    "        for j in arr:\n",
    "            if i == j:\n",
    "                continue\n",
    "            if (i + j) == target:\n",
    "                results.append(tuple([i, j]))\n",
    "    \n",
    "    return list(set(results))\n",
    "\n",
    "findSum([1, 2, 3, 4, 5], 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 5), (3, 4)]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Method 2\n",
    "def findSum(arr, target): # Time Complexity: O(log(n) + n) => O(n)\n",
    "    arr.sort()\n",
    "    results = []\n",
    "    low = 0 \n",
    "    high = len(arr) - 1\n",
    "    while (low < high):\n",
    "        if (arr[low] + arr[high]) == target:\n",
    "            results.append(tuple([arr[low], arr[high]]))\n",
    "        \n",
    "        if (arr[low] + arr[high]) < target:\n",
    "            low += 1\n",
    "\n",
    "        else:\n",
    "            high -= 1\n",
    "    return results\n",
    "findSum([2, 1, 3, 4, 5], 7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 3\n",
    "Given an integer array of range in with length (n + 1), find the duplicate number.\n",
    "- Input: [1, 2, 3, 4, 5, 5, 6]\n",
    "- Output: 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Method 1\n",
    "def findDuplicate(arr): # Time complexity: O(n), Space complexity: O(n)\n",
    "    data = {}\n",
    "    for element in arr:\n",
    "        if element not in data:\n",
    "            data[element] = 0\n",
    "        data[element] += 1\n",
    "\n",
    "    for key, value in data.items():\n",
    "        if value > 1:\n",
    "            return key\n",
    "\n",
    "findDuplicate([1, 2, 3, 4, 5, 5, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Method 2\n",
    "def findDuplicate(arr): # Time complexity: O(n), Space complexity: O(n)\n",
    "    data = []\n",
    "    for element in arr:\n",
    "        if element in data:\n",
    "            return element\n",
    "        else:\n",
    "            data.append(element)\n",
    "\n",
    "findDuplicate([1, 2, 3, 4, 5, 5, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 4\n",
    "Given two lists, check whether the lists are a permutation of each other. Note, you must not use the `.sort()` function.\n",
    "- Input_1: [1, 2, 3, 4], [4, 3, 1, 2]\n",
    "- Output_1: True\n",
    "- Input_2: [\"a\", \"c\", \"b\"], [\"j\", \"c\", \"b\"]\n",
    "- Output_2: False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def isPermutation(list_1, list_2):\n",
    "    if len(list_1) != len(list_2):\n",
    "        return False\n",
    "\n",
    "    count = len([element for element in list_1 if element in list_2])\n",
    "    if count == len(list_1):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "print(isPermutation([1, 2, 3, 4], [4, 3, 1, 2]))\n",
    "print(isPermutation([\"a\", \"c\", \"b\"], [\"j\", \"c\", \"b\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "40d3a090f54c6569ab1632332b64b2c03c39dcf918b08424e98f38b5ae0af88f"
  },
  "kernelspec": {
   "display_name": "Python 3.8.3 ('base')",
   "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.3"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}