interactive-coding-challenges/online_judges/mult_other_numbers/mult_other_numbers_solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solution Notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: Given a list of ints, find the products of every other int for each index.\n",
    "\n",
    "* [Constraints](#Constraints)\n",
    "* [Test Cases](#Test-Cases)\n",
    "* [Algorithm](#Algorithm)\n",
    "* [Code](#Code)\n",
    "* [Unit Test](#Unit-Test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constraints\n",
    "\n",
    "* Can we use division?\n",
    "    * No\n",
    "* Is the output a list of ints?\n",
    "    * Yes\n",
    "* Can we assume the inputs are valid?\n",
    "    * No\n",
    "* Can we assume this fits memory?\n",
    "    * Yes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Cases\n",
    "\n",
    "<pre>\n",
    "* None -> TypeError\n",
    "* [] -> []\n",
    "* [0] -> []\n",
    "* [0, 1] -> [1, 0]\n",
    "* [0, 1, 2] -> [2, 0, 0]\n",
    "* [1, 2, 3, 4] -> [24, 12, 8, 6]\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm\n",
    "\n",
    "### Brute force:\n",
    "\n",
    "<pre>\n",
    "sum = 1\n",
    " |\n",
    "[1, 2, 3, 4]\n",
    " ^\n",
    "skip if both pointers are pointing to the same spot\n",
    "    |\n",
    "[1, 2, 3, 4]\n",
    " ^\n",
    "sum *= 2\n",
    "       |\n",
    "[1, 2, 3, 4]\n",
    " ^\n",
    "sum *= 3\n",
    "          |\n",
    "[1, 2, 3, 4]\n",
    " ^\n",
    "sum *= 4\n",
    "results.append(sum)\n",
    "results = [24]\n",
    "\n",
    "repeat for every element in the input list to obtain:\n",
    "\n",
    "[24, 12, 8, 6]\n",
    " \n",
    "</pre>\n",
    "\n",
    "Complexity:\n",
    "* Time: O(n^2)\n",
    "* Space: O(n)\n",
    "\n",
    "### Greedy\n",
    "\n",
    "<pre>\n",
    "input  = [1, 2, 3, 4]\n",
    "result = [2*3*4, 1*3*4, 1*2*4, 1*2*3]\n",
    "\n",
    "Note we are duplicating multiplications with the brute force approach.\n",
    "\n",
    "We'll calculate all products before an index, and all products after an index.\n",
    "We'll then multiple these two together to form the result.\n",
    "\n",
    "input  = [1,         2,     3,     4]\n",
    "before = [1,         1,   1*2, 1*2*3]\n",
    "after  = [2*3*4, 1*3*4, 1*2*4,     1]\n",
    "result = [   24,    12,     8,     6] \n",
    "</pre>\n",
    "\n",
    "Complexity:\n",
    "* Time: O(n)\n",
    "* Space: O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "\n",
    "    def mult_other_numbers_brute(self, array):\n",
    "        if array is None:\n",
    "            raise TypeError('array cannot be None')\n",
    "        if not array:\n",
    "            return array\n",
    "        if len(array) == 1:\n",
    "            return []\n",
    "        result = []\n",
    "        for i in range(len(array)):\n",
    "            curr_sum = 1\n",
    "            for j in range(len(array)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                curr_sum *= array[j]\n",
    "            result.append(curr_sum)\n",
    "        return result\n",
    "\n",
    "    def mult_other_numbers(self, array):\n",
    "        if array is None:\n",
    "            raise TypeError('array cannot be None')\n",
    "        if not array:\n",
    "            return array\n",
    "        if len(array) == 1:\n",
    "            return []\n",
    "        result = [None] * len(array)\n",
    "        curr_product = 1\n",
    "        for i in range(len(array)):\n",
    "            result[i] = curr_product\n",
    "            curr_product *= array[i]\n",
    "        curr_product = 1\n",
    "        for i in range(len(array))[::-1]:\n",
    "            result[i] *= curr_product\n",
    "            curr_product *= array[i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unit Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting test_mult_other_numbers.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile test_mult_other_numbers.py\n",
    "import unittest\n",
    "\n",
    "\n",
    "class TestMultOtherNumbers(unittest.TestCase):\n",
    "\n",
    "    def test_mult_other_numbers(self):\n",
    "        solution = Solution()\n",
    "        self.assertRaises(TypeError, solution.mult_other_numbers, None)\n",
    "        self.assertEqual(solution.mult_other_numbers([0]), [])\n",
    "        self.assertEqual(solution.mult_other_numbers([0, 1]), [1, 0])\n",
    "        self.assertEqual(solution.mult_other_numbers([0, 1, 2]), [2, 0, 0])\n",
    "        self.assertEqual(solution.mult_other_numbers([1, 2, 3, 4]), [24, 12, 8, 6])\n",
    "        print('Success: test_mult_other_numbers')\n",
    "\n",
    "\n",
    "def main():\n",
    "    test = TestMultOtherNumbers()\n",
    "    test.test_mult_other_numbers()\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success: test_mult_other_numbers\n"
     ]
    }
   ],
   "source": [
    "%run -i test_mult_other_numbers.py"
   ]
  }
 ],
 "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}