Math.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solution usually involves mathematical analysis."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8. String to Integer (atoi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement atoi to convert a string to an integer.\n",
    "\n",
    "Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.\n",
    "\n",
    "Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.\n",
    "\n",
    "**Requirements for atoi**:\n",
    "\n",
    "The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.\n",
    "\n",
    "The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.\n",
    "\n",
    "If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.\n",
    "\n",
    "If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def myAtoi(self, str):\n",
    "        \"\"\"\n",
    "        :type str: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(str)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        start=0\n",
    "        positive=True\n",
    "        sign=False\n",
    "        for i in xrange(n):\n",
    "            if sign==True and not str[i].isdigit():\n",
    "                return 0\n",
    "            if str[i]==' ':\n",
    "                start+=1\n",
    "            if (str[i]=='-' or str[i]=='+'):\n",
    "                sign=True\n",
    "                positive=(str[i]=='+')\n",
    "                start+=1\n",
    "            if str[i].isdigit():\n",
    "                break\n",
    "        \n",
    "        result=0\n",
    "        for i in xrange(start,n):\n",
    "            if not str[i].isdigit():\n",
    "                break\n",
    "            result=10*result+int(str[i])\n",
    "            \n",
    "        if not positive:\n",
    "            result=-result\n",
    "        return min(max(-2147483648, result), 2147483647)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "str=\"    010\"\n",
    "o.myAtoi(str)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 29. Divide Two Integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Divide two integers without using multiplication, division and mod operator.\n",
    "\n",
    "If it is overflow, return MAX_INT."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We can implement the division by recursively subtract the divisor from the dividend."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def divide(self, dividend, divisor):\n",
    "        \"\"\"\n",
    "        :type dividend: int\n",
    "        :type divisor: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if divisor==0:\n",
    "            return 2147483647\n",
    "        positive=(dividend < 0) is (divisor < 0)\n",
    "        dividend, divisor=abs(dividend), abs(divisor)\n",
    "        res=0\n",
    "        while dividend>=divisor:\n",
    "            res+=1\n",
    "            dividend-=divisor\n",
    "        if not positive:\n",
    "            res=-res\n",
    "        return min(max(-2147483648, res), 2147483647)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.divide(-2,-3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE for the test case -2147483648/(-1). It can be improved by bit manipulation as the maximum integer is 2^31-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def divide(self, dividend, divisor):\n",
    "        \"\"\"\n",
    "        :type dividend: int\n",
    "        :type divisor: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if divisor==0:\n",
    "            return 2147483647\n",
    "        positive=(dividend < 0) is (divisor < 0)\n",
    "        dividend, divisor=abs(dividend), abs(divisor)\n",
    "        res=0\n",
    "        while dividend>=divisor:\n",
    "            temp,i=divisor,1\n",
    "            while dividend>=temp:\n",
    "                dividend-=temp\n",
    "                res+=i\n",
    "                temp<<=1\n",
    "                i<<=1\n",
    "        if not positive:\n",
    "            res=-res\n",
    "        return min(max(-2147483648, res), 2147483647)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2147483647"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.divide(1,0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 43. Multiply Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.\n",
    "\n",
    "Note:\n",
    "\n",
    "1. The length of both num1 and num2 is < 110.\n",
    "2. Both num1 and num2 contains only digits 0-9.\n",
    "3. Both num1 and num2 does not contain any leading zero.\n",
    "4. You must not use any built-in BigInteger library or convert the inputs to integer directly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def multiply(self, num1, num2):\n",
    "        \"\"\"\n",
    "        :type num1: str\n",
    "        :type num2: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        length1=len(num1)\n",
    "        length2=len(num2)\n",
    "        num1_int=0\n",
    "        num2_int=0\n",
    "        for i in xrange(length1):\n",
    "            num1_int=10*num1_int+int(num1[i])\n",
    "        for i in xrange(length2):\n",
    "            num2_int=10*num2_int+int(num2[i])\n",
    "        product=num1_int*num2_int\n",
    "        result=''\n",
    "        if product==0:\n",
    "            return '0'\n",
    "        while product>0:\n",
    "            res=product%10\n",
    "            result=str(res)+result\n",
    "            product=product//10\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'65'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "num1='1'\n",
    "num2='65'\n",
    "o.multiply(num1,num2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'str' object is not callable",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-90-d77a1c69f9e5>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mstr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'str' object is not callable"
     ]
    }
   ],
   "source": [
    "str(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 60. Permutation Sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The set [1,2,3,…,n] contains a total of n! unique permutations.\n",
    "\n",
    "By listing and labeling all of the permutations in order,\n",
    "We get the following sequence (ie, for n = 3):\n",
    "\n",
    "\"123\"\n",
    "\n",
    "\"132\"\n",
    "\n",
    "\"213\"\n",
    "\n",
    "\"231\"\n",
    "\n",
    "\"312\"\n",
    "\n",
    "\"321\"\n",
    "\n",
    "Given n and k, return the kth permutation sequence.\n",
    "\n",
    "Note: Given n will be between 1 and 9 inclusive."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Let me examine another example: n=4\n",
    "\n",
    "\"1234\"\n",
    "\n",
    "\"1243\"\n",
    "\n",
    "\"1324\"\n",
    "\n",
    "\"1342\"\n",
    "\n",
    "\"1423\"\n",
    "\n",
    "\"1432\"\n",
    "\n",
    "\"2134\"\n",
    "\n",
    "\"2143\"\n",
    "\n",
    "\"2314\"\n",
    "\n",
    "\"2341\"\n",
    "\n",
    "\"2413\"\n",
    "\n",
    "\"2431\"\n",
    "\n",
    "\"3124\"\n",
    "\n",
    "\"3142\"\n",
    "\n",
    "\"3214\"\n",
    "\n",
    "\"3241\"\n",
    "\n",
    "\"3412\"\n",
    "\n",
    "\"3421\"\n",
    "\n",
    "...\n",
    "\n",
    "Given permutation from set [1,...,n-1], we could construct [1,...,n] as follows:\n",
    "\n",
    "permutations=[[]]\n",
    "for m in xrange(1,n+1):\n",
    "     initial=[1,2,...,m]\n",
    "     result=[]\n",
    "     for i in xrange(len(initial)):\n",
    "          temp=initial[:i]+initial[i+1:]\n",
    "          result+=[[initial[i]]+[temp[j-1] for j in permutation] for permutation in permutations]\n",
    "     permutations=result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def getPermutation(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        permutations=[[]]\n",
    "        for m in xrange(1,n+1):\n",
    "            initial=range(1,m+1)\n",
    "            result=[]\n",
    "            for i in xrange(len(initial)):\n",
    "                temp=initial[:i]+initial[i+1:]\n",
    "                result+=[[initial[i]]+[temp[j-1] for j in permutation] for permutation in permutations]\n",
    "            permutations=result\n",
    "        return ''.join([str(num) for num in permutations[k-1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'213'"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.getPermutation(3,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE. The idea is as follow:\n",
    "\n",
    "For permutations of n, the first (n-1)! permutations start with 1, next (n-1)! ones start with 2, ... and so on. And in each group of (n-1)! permutations, the first (n-2)! permutations start with the smallest remaining number, ...\n",
    "\n",
    "take n = 3 as an example, the first 2 (that is, (3-1)! ) permutations start with 1, next 2 start with 2 and last 2 start with 3. For the first 2 permutations (123 and 132), the 1st one (1!) starts with 2, which is the smallest remaining number (2 and 3). So we can use a loop to check the region that the sequence number falls in and get the starting digit. Then we adjust the sequence number and continue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "class Solution(object):\n",
    "    def getPermutation(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        result=[]\n",
    "        nums=range(1,n+1)\n",
    "        k-=1\n",
    "        for i in xrange(n,0,-1):\n",
    "            index=k//math.factorial(i-1)\n",
    "            result.append(nums[index])\n",
    "            nums.pop(index)\n",
    "            k=k%math.factorial(i-1)\n",
    "            \n",
    "        return ''.join([str(num) for num in result])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'132'"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.getPermutation(3,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "math.factorial(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 166. Fraction to Recurring Decimal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.\n",
    "\n",
    "If the fractional part is repeating, enclose the repeating part in parentheses.\n",
    "\n",
    "For example,\n",
    "\n",
    "Given numerator = 1, denominator = 2, return \"0.5\".\n",
    "\n",
    "Given numerator = 2, denominator = 1, return \"2\".\n",
    "\n",
    "Given numerator = 2, denominator = 3, return \"0.(6)\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hint:\n",
    "\n",
    "* No scary math, just apply elementary math knowledge. Still remember how to perform a long division?\n",
    "* Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?\n",
    "* Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The difficulty lies in how to capture the repeating part. I will try to use the hashtable recording the residuals to do the job. We also need to consider how to add the floating point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def fractionToDecimal(self, numerator, denominator):\n",
    "        \"\"\"\n",
    "        :type numerator: int\n",
    "        :type denominator: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        # check if denominator is zero\n",
    "        if denominator==0:\n",
    "            return None\n",
    "        # numerator=0\n",
    "        if numerator==0:\n",
    "            return '0'\n",
    "        # hashtable to record the residuals and their \n",
    "        num_dict={}\n",
    "        result=''\n",
    "        # return the result digit by digit\n",
    "        # float point indicator\n",
    "        float_point=True\n",
    "        # position variable to record residuals appeared\n",
    "        pos=0\n",
    "        while numerator>0:\n",
    "            d=numerator//denominator\n",
    "            res=numerator%denominator\n",
    "            # add float point after the integer\n",
    "            if float_point:\n",
    "                result+=str(d)\n",
    "                if res>0:\n",
    "                    result+='.'\n",
    "                    pos+=1\n",
    "                float_point=False\n",
    "            else:\n",
    "                # already have the residual\n",
    "                if num_dict.get(res):\n",
    "                    result+=str(d)\n",
    "                    left=num_dict.get(res)\n",
    "                    result=result[:left]+'('+result[left:]\n",
    "                    result+=')'\n",
    "                    break\n",
    "                else: # residual not yet encountered\n",
    "                    result+=str(d)\n",
    "            # numerator for next loop\n",
    "            pos+=len(str(d))\n",
    "            num_dict[res]=pos\n",
    "            numerator=res*10\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0.(428571)'"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.fractionToDecimal(3,7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution fails to consider the negative number. Let me add the case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def fractionToDecimal(self, numerator, denominator):\n",
    "        \"\"\"\n",
    "        :type numerator: int\n",
    "        :type denominator: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        # check if denominator is zero\n",
    "        if denominator==0:\n",
    "            return None\n",
    "        # numerator=0\n",
    "        if numerator==0:\n",
    "            return '0'\n",
    "        # determine sign of the solution:\n",
    "        negative=False\n",
    "        if denominator/abs(denominator)!=numerator/abs(numerator):\n",
    "            negative=True\n",
    "        numerator=abs(numerator)\n",
    "        denominator=abs(denominator)\n",
    "        # hashtable to record the residuals and their \n",
    "        num_dict={}\n",
    "        result=''\n",
    "        # return the result digit by digit\n",
    "        # float point indicator\n",
    "        float_point=True\n",
    "        # position variable to record residuals appeared\n",
    "        pos=0\n",
    "        while numerator>0:\n",
    "            d=numerator//denominator\n",
    "            res=numerator%denominator\n",
    "            # add float point after the integer\n",
    "            if float_point:\n",
    "                result+=str(d)\n",
    "                if res>0:\n",
    "                    result+='.'\n",
    "                    pos+=1\n",
    "                float_point=False\n",
    "            else:\n",
    "                # already have the residual\n",
    "                if num_dict.get(res):\n",
    "                    result+=str(d)\n",
    "                    left=num_dict.get(res)\n",
    "                    result=result[:left]+'('+result[left:]\n",
    "                    result+=')'\n",
    "                    break\n",
    "                else: # residual not yet encountered\n",
    "                    result+=str(d)\n",
    "            # numerator for next loop\n",
    "            pos+=len(str(d))\n",
    "            num_dict[res]=pos\n",
    "            numerator=res*10\n",
    "        if negative:\n",
    "            result='-'+result\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0.(6)'"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.fractionToDecimal(2,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 172. Factorial Trailing Zeroes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer n, return the number of trailing zeroes in n!.\n",
    "\n",
    "Note: Your solution should be in logarithmic time complexity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The idea is to count the number of pairs of factors 2 and 5, Since the number of factor 5 is always less than 2 in n!, we can do binary search based on the divisor 5. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def trailingZeroes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count_zero=0\n",
    "        while n>0:\n",
    "            n=n/5\n",
    "            count_zero+=n\n",
    "            \n",
    "        return count_zero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.trailingZeroes(25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 204. Count Primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description:\n",
    "\n",
    "Count the number of prime numbers less than a non-negative number, n."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First we create a list of size less than or equal to n and store the boolean values. We first cross off 0 and 1. Then we cross off multiples of 2 and find the next prime is 3. Then we cross off multiples of 3 with multiples larger or equal to 3. We only need to consider primes up to sqrt(n). Time complexity analysis: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def countPrimes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n<2:\n",
    "            return 0\n",
    "        primes=[True]*n\n",
    "        primes[0]=primes[1]=False\n",
    "        p=2\n",
    "        while (p*p)<n:\n",
    "            i=p\n",
    "            while (i*p)<n:\n",
    "                j=i*p\n",
    "                if primes[j]:\n",
    "                    primes[j]=False\n",
    "                i+=1\n",
    "            p+=1\n",
    "            while (p*p)<n and not primes[p]:\n",
    "                p+=1\n",
    "        return sum(primes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1229"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.countPrimes(10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution turns out to be wrong for 10000."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def findPrimes(max):\n",
    "    checklist=[True]*(max)\n",
    "    checklist[0]=checklist[1]=False\n",
    "    prime=2\n",
    "    while prime*prime<max:\n",
    "        crossoff(checklist,prime)\n",
    "        prime=findnextPrime(checklist,prime)\n",
    "    return checklist\n",
    "\n",
    "def crossoff(checklist,prime):\n",
    "    for num in range(prime*prime,len(checklist)):\n",
    "        if num%prime==0:\n",
    "            checklist[num]=False\n",
    "            \n",
    "def findnextPrime(checklist,prime):\n",
    "    for num in range(prime+1,len(checklist)):\n",
    "        if checklist[num]:\n",
    "            return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1229"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(findPrimes(10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 223. Rectangle Area"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the total area covered by two rectilinear rectangles in a 2D plane.\n",
    "\n",
    "Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.\n",
    "\n",
    "<img src=https://leetcode.com/static/images/problemset/rectangle_area.png>\n",
    "\n",
    "Assume that the total area is never beyond the maximum possible value of int."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: If the two rectangles do not touch, then total area=area1+area2; if there is overlap, then we subtract the overlap area. How to determine overlap? We need to determine the overlap range between [A,C] and [E,G], between [B,D] and [F,H]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def computeArea(self, A, B, C, D, E, F, G, H):\n",
    "        \"\"\"\n",
    "        :type A: int\n",
    "        :type B: int\n",
    "        :type C: int\n",
    "        :type D: int\n",
    "        :type E: int\n",
    "        :type F: int\n",
    "        :type G: int\n",
    "        :type H: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a=0\n",
    "        b=0\n",
    "        if A<=E:\n",
    "            if E<=min(C,G):\n",
    "                a=min(C,G)-E\n",
    "        else:\n",
    "            if A<=min(C,G):\n",
    "                a=min(C,G)-A\n",
    "                \n",
    "        if B<=F:\n",
    "            if F<=min(D,H):\n",
    "                b=min(D,H)-F\n",
    "        else:\n",
    "            if B<=min(D,H):\n",
    "                b=min(D,H)-B\n",
    "                \n",
    "        return (C-A)*(D-B)+(G-E)*(H-F)-a*b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.computeArea(-3,0,3,4,0,-1,9,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 258. Add Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.\n",
    "\n",
    "For example:\n",
    "\n",
    "Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.\n",
    "\n",
    "Follow up:\n",
    "Could you do it without any loop/recursion in O(1) runtime?\n",
    "\n",
    "Hint:\n",
    "\n",
    "* A naive implementation of the above process is trivial. Could you come up with other methods?\n",
    "* What are all the possible results?\n",
    "* How do they occur, periodically or randomly?\n",
    "* You may find this Wikipedia article useful.\n",
    "\n",
    "https://en.wikipedia.org/wiki/Digital_root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The output can only be 0 to 9. It helps to see the digital root of a positive integer as the position it holds with respect to the largest multiple of 9 less than the number itself. For example, the digital root of 11 is 2, which means that 11 is the second number after 9. Likewise, the digital root of 2035 is 1, which means that 2035 − 1 is a multiple of 9. If a number produces a digital root of exactly 9, then the number is a multiple of 9.\n",
    "\n",
    "With this in mind the digital root of a positive integer n is\n",
    "\n",
    "$$\n",
    "dr[n]=n-9 \\times (n//9)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def addDigits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if num==0:\n",
    "            return 0\n",
    "        if num%9>0:\n",
    "            dr=num-9*(num//9)\n",
    "        else:\n",
    "            dr=num-9*((num-1)//9)\n",
    "        return dr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.addDigits(18)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "reference solution: https://leetcode.com/problems/add-digits/?tab=Solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 263. Ugly Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a program to check whether a given number is an ugly number.\n",
    "\n",
    "Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.\n",
    "\n",
    "Note that 1 is typically treated as an ugly number."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Ugly number by definition can be devided repeatedly by num in [2,3,5] until it becomes 1. This is because any non-prime factors can be break down into prime factors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that for num<=0, it is false."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isUgly(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if num<=0:\n",
    "            return False\n",
    "        for factor in [2,3,5]:\n",
    "            while num%factor==0:\n",
    "                num/=factor\n",
    "                \n",
    "        return num==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.isUgly(14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 264. Ugly Number II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a program to find the n-th ugly number.\n",
    "\n",
    "Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.\n",
    "\n",
    "Note that 1 is typically treated as an ugly number."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: For this problem we probably need to consider dynamic programming. We need to store the results in 3 queues Q2, Q3, Q5 and then dequeue their first elements and to find the next minimum ugly number from min(Q2[0],Q3[0],Q5[0])."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that Q2 only contains factor of 2; Q3 contains factors 3 and 2; Q5 contains factors 2,3,5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def nthUglyNumber(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n<=0:\n",
    "            return None\n",
    "        # ugly numbers list\n",
    "        ugly_list=[1]\n",
    "        # initialize Q2,Q3,Q5\n",
    "        Q2=[2]\n",
    "        Q3=[3]\n",
    "        Q5=[5]\n",
    "        while len(ugly_list)<n:\n",
    "            # next minimum\n",
    "            next_min=min(Q2[0],Q3[0],Q5[0])\n",
    "            if next_min==Q2[0]:\n",
    "                ugly_list.append(Q2.pop(0))\n",
    "                Q2.append(next_min*2)\n",
    "                Q3.append(next_min*3)\n",
    "                Q5.append(next_min*5)\n",
    "            elif next_min==Q3[0]:\n",
    "                ugly_list.append(Q3.pop(0))\n",
    "                Q3.append(next_min*3)\n",
    "                Q5.append(next_min*5)\n",
    "            else:\n",
    "                ugly_list.append(Q5.pop(0))\n",
    "                Q5.append(next_min*5)\n",
    "        return ugly_list[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 170,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.nthUglyNumber(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 319. Bulb Switcher"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.\n",
    "\n",
    "Example:\n",
    "\n",
    "Given n = 3. \n",
    "\n",
    "At first, the three bulbs are [off, off, off].\n",
    "After first round, the three bulbs are [on, on, on].\n",
    "After second round, the three bulbs are [on, off, on].\n",
    "After third round, the three bulbs are [on, off, off]. \n",
    "\n",
    "So you should return 1, because there is only one bulb is on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: For the nth bulb, whether it is on or off at the end depends on how many times it is toggled. and it just depend on how many factors it has for 1<=m<=n. So we can easily come up with an O(n^2) solution by using nested for loops. Can we do better? If we already knew the configuration for n-1, we only need to know if the nth bulb is on or off."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "class Solution(object):\n",
    "    def bulbSwitch(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count=0\n",
    "        for i in xrange(1,n+1):\n",
    "            flip=0\n",
    "            for j in xrange(1,i+1):\n",
    "                if i%j==0:\n",
    "                    flip+=1\n",
    "            if flip%2!=0:\n",
    "                count+=1\n",
    "        return count,int(math.sqrt(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(22, 22)"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.bulbSwitch(503)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE. The key is to know if the number of factors for bulb i is even or odd. Notice that for every i the factors always comes in pairs except that the number i it self is a perfect square. So the problem reduces to counting the number of perfect squares less than or equal to i, which is just int(sqrt(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "class Solution(object):\n",
    "    def bulbSwitch(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return int(math.sqrt(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 326. Power of Three"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer, write a function to determine if it is a power of three.\n",
    "\n",
    "Follow up:\n",
    "\n",
    "Could you do it without using any loop / recursion?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Naive solution is to check $3^i==n, i=0,1,2,...$. The time complexity is O(log n). Now consider doing it without any loop/recursion. \n",
    "\n",
    "Editorial solution: Integer Limitations\n",
    "\n",
    "MaxInt = 2^31-1 since we use 32 bits to represent the number, half of the range is used for negative numbers and 0 is part of the positive numbers. Knowing the limitation of n, we can now deduce that the maximum value of n that is also a power of three is 1162261467. Therefore, the possible values of n where we should return true are $3^0, 3^1,...,3^{19}$. Since 3 is a prime number, the only divisors of $3^{19}$ are \n",
    "$3^0, 3^1,...,3^{19}$, therefore all we need to do is divide $3^{19}$ by n. A remainder of 0 means n is a divisor of \n",
    "$3^{19}$ and therefore a power of three."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isPowerOfThree(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if n<=0:\n",
    "            return False\n",
    "        return 3**19%n==0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above code takes time in evaluating 3^19. So we should replace it with 1162261467."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isPowerOfThree(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return n>0 and 1162261467%n==0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 365. Water and Jug Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.\n",
    "\n",
    "If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.\n",
    "\n",
    "Operations allowed:\n",
    "\n",
    "* Fill any of the jugs completely with water.\n",
    "* Empty any of the jugs.\n",
    "* Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.\n",
    "\n",
    "Example 1: (From the famous \"Die Hard\" example)\n",
    "\n",
    "Input: x = 3, y = 5, z = 4\n",
    "\n",
    "Output: True\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: x = 2, y = 6, z = 5\n",
    "\n",
    "Output: False\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: If z can be measured, then\n",
    "$$\n",
    "z=m*x+n*y, m,n \\in Z\\ and\\ m*x+n*y\\geq0\n",
    "$$\n",
    "\n",
    "Without loss of generality, assume $y \\geq x$:\n",
    "\n",
    "1. if y%x==0, then $z=l*x$.\n",
    "2. if y%x!=0, we can compute the residuals y=q*x+c, then\n",
    "$$\n",
    "z=m*c+n*x\n",
    "$$\n",
    "\n",
    "if c==1, we know we can measure z. Otherwise, we set y=x, x=c, and do it recursively"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canMeasureWater(self, x, y, z):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :type y: int\n",
    "        :type z: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if z>x+y:\n",
    "            return False\n",
    "        large=max(x,y)\n",
    "        small=min(x,y)\n",
    "        while small!=0 and small!=1:\n",
    "            residual=large%small\n",
    "            large=small\n",
    "            small=residual\n",
    "            \n",
    "        if small==1:\n",
    "            return True\n",
    "        elif large==0:\n",
    "            return z==0\n",
    "        else:\n",
    "            return z%large==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.canMeasureWater(2,4,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that if z>x+y, we will never be able to measure the water by just using the two jugs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 367. Valid Perfect Square"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a positive integer num, write a function which returns True if num is a perfect square else False.\n",
    "\n",
    "Note: Do not use any built-in library function such as sqrt.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: 16\n",
    "\n",
    "Returns: True\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: 14\n",
    "\n",
    "Returns: False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The naive solution run time will be O(n^(1/2))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isPerfectSquare(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        k=1\n",
    "        while k*k<num:\n",
    "            k+=1\n",
    "        return (k*k)==num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.isPerfectSquare(14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One improvement is to use binary search. Then the runtime will be O(log n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isPerfectSquare(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        start=1\n",
    "        end=num\n",
    "        while start<=end:\n",
    "            mid=(start+end)/2\n",
    "            if (mid*mid)<num:\n",
    "                start=mid+1\n",
    "            elif (mid*mid)>num:\n",
    "                end=mid-1\n",
    "            else:\n",
    "                return True\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.isPerfectSquare(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 372. Super Pow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your task is to calculate $a^b$ mod 1337 where $a$ is a positive integer and $b$ is an extremely large positive integer given in the form of an array.\n",
    "\n",
    "Example1:\n",
    "\n",
    "a = 2\n",
    "b = [3]\n",
    "\n",
    "Result: 8\n",
    "\n",
    "Example2:\n",
    "\n",
    "a = 2\n",
    "b = [1,0]\n",
    "\n",
    "Result: 1024"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: To calculate the power one by one, we can start from the end of the list and do the following:\n",
    "\n",
    "a=2,b=[1,1,4]\n",
    "$$\n",
    "power=(2^1)^{(10^2)}*(2^1)^{(10^1)}*(2^4)^{(10^0)}\n",
    "$$\n",
    "\n",
    "In order to solve the mod part, the knowledge is\n",
    "\n",
    "$$\n",
    "(a*b)%k=(a%k)*(b%k)%k\n",
    "$$\n",
    "\n",
    "Then\n",
    "\n",
    "f(a,[b1,b2...bn])=(f(a,[b1,b2...0])*(a^bn%k))%k\n",
    "=(f(f(a,[b1,b2...bn-1]),10)*(a^bn%k))%k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def superPow(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: int\n",
    "        :type b: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(b)\n",
    "        if n==1:\n",
    "            return (a**b[0])%1337\n",
    "        return self.superPow(self.superPow(a, b[:n-1]),[10])*((a**b[-1])%1337)%1337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "368"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.superPow(2,[2,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 396. <font color=red>Rotate Function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array of integers A and let n to be its length.\n",
    "\n",
    "Assume $B_k$ to be an array obtained by rotating the array $A_k$ positions clock-wise, we define a \"rotation function\" F on A as follow:\n",
    "$$\n",
    "F(k) = 0 * B_k[0] + 1 * B_k[1] + ... + (n-1) * B_k[n-1].\n",
    "$$\n",
    "Calculate the maximum value of F(0), F(1), ..., F(n-1).\n",
    "\n",
    "Note:\n",
    "n is guaranteed to be less than 105.\n",
    "\n",
    "Example:\n",
    "\n",
    "A = [4, 3, 2, 6]\n",
    "$$\n",
    "F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25 \\\\\n",
    "F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16 \\\\\n",
    "F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23 \\\\\n",
    "F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26\n",
    "$$\n",
    "So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal Force solution takes O(n^2)=O(n) times O(n). We can do better with the following consideration:\n",
    "\n",
    "F(0)=0∗A[0]+1∗A[1]+...+(n−1)∗A[n−1]\n",
    "\n",
    "F(k)=F(k-1)+total_sum-A[n-k]-(n-1)A[n-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maxRotateFunction(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(A)\n",
    "        total_sum=sum(A)\n",
    "        f=0\n",
    "        for i in xrange(n):\n",
    "            f+=i*A[i]\n",
    "        maximum=f\n",
    "        for i in xrange(1,n):\n",
    "            f=f+total_sum-A[n-i]-(n-1)*A[n-i]\n",
    "            if f>maximum:\n",
    "                maximum=f\n",
    "                \n",
    "        return maximum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "26"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "A=[4,3,2,6]\n",
    "o.maxRotateFunction(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 397. Integer Replacement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a positive integer n and you can do operations as follow:\n",
    "\n",
    "1. If n is even, replace n with n/2.\n",
    "2. If n is odd, you can replace n with either n + 1 or n - 1.\n",
    "\n",
    "What is the minimum number of replacements needed for n to become 1?\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "8\n",
    "\n",
    "Output:\n",
    "3\n",
    "\n",
    "Explanation:\n",
    "8 -> 4 -> 2 -> 1\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "7\n",
    "\n",
    "Output:\n",
    "4\n",
    "\n",
    "Explanation:\n",
    "7 -> 8 -> 4 -> 2 -> 1\n",
    "or\n",
    "7 -> 6 -> 3 -> 2 -> 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: A DP solution is possible according to the following recursion:\n",
    "\n",
    "min_num_replacements[n]=1+min_num_replacements[n/2] for n even\n",
    "\n",
    "min_num_replacements[n]=2+min(min_num_replacements[(n+1)/2],min_num_replacements[(n-1)/2])\n",
    "\n",
    "Base case:\n",
    "\n",
    "min_num_replacements[1]=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def integerReplacement(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums=[0]*(n+1)\n",
    "        for i in xrange(2,n+1):\n",
    "            if i%2==0:\n",
    "                nums[i]=1+nums[i/2]\n",
    "            else:\n",
    "                nums[i]=2+min(nums[(i+1)/2],nums[(i-1)/2])\n",
    "                \n",
    "        return nums[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.integerReplacement(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE. One improvement to O(log n) is by Bit manipulation: For this problem, if we look at the binary form of each number, we can get the idea that for each '1' (except for the first '1') it counts to two steps, for each '0', it counts to one step.\n",
    "So our goal is to use +1 or -1 to reduce steps.\n",
    "\n",
    "For example,\n",
    "13 = 1101\n",
    "If we plus one, we can get 1110; if we reduce one, we can get 1100;\n",
    "1110 needs 2+2+1 = 5 steps, while 1100 only needs 2+1+1 = 4 steps, so we choose n-1 in this step.\n",
    "\n",
    "Based on the above analysis, we will look at the last two bits of $n$ if $n$ is odd. If last two digits are '01', then we move to n-1; if the last two digits are '11', then we move to n+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def integerReplacement(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count=0\n",
    "        while n>1:\n",
    "            count+=1\n",
    "            if n%2==0:\n",
    "                n=n/2\n",
    "            elif n&2==2:\n",
    "                n+=1\n",
    "            else:\n",
    "                n-=1\n",
    "                \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.integerReplacement(13)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is wrong for n==3, which is a special case to be considered."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def integerReplacement(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count=0\n",
    "        while n>3:\n",
    "            count+=1\n",
    "            if n%2==0:\n",
    "                n=n/2\n",
    "            elif n&2==2:\n",
    "                n+=1\n",
    "            else:\n",
    "                n-=1\n",
    "        if n==3:\n",
    "            count+=2\n",
    "        elif n==2:\n",
    "            count+=1\n",
    "            \n",
    "        return count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 400. Nth Digit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...\n",
    "\n",
    "Note:\n",
    "n is positive and will fit within the range of a 32-bit signed integer (n < 2^31).\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "3\n",
    "\n",
    "Output:\n",
    "3\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "11\n",
    "\n",
    "Output:\n",
    "0\n",
    "\n",
    "Explanation:\n",
    "\n",
    "The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First we locate the number of digits of the number that contains the nth digit. Then we locate the number that contains the nth digit. Last we locate the digit.\n",
    "\n",
    "\n",
    "single digit numbers: 9; two digit numbers: 90; 3 digits numbers: 900; 4 digits numbers: 9000 ... k digits number: 9*10^(k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findNthDigit(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # locate the number of digits of the number contains the nth digit\n",
    "        k=1\n",
    "        while n>k*9*10**(k-1):\n",
    "            n-=k*9*10**(k-1)\n",
    "            k+=1\n",
    "        # locate the number that contains the nth digit and extract the digit\n",
    "        result=-1\n",
    "        if n%k==0:\n",
    "            i=n//k\n",
    "            num=10**(k-1)-1+i\n",
    "            result=num%10\n",
    "        else:\n",
    "            m=n%k\n",
    "            i=n//k+1\n",
    "            num=10**(k-1)-1+i\n",
    "            # extract mth digit from left\n",
    "            num=num//10**(k-m)\n",
    "            result=num%10\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.findNthDigit(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 415. Add Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2.\n",
    "\n",
    "Note:\n",
    "\n",
    "* The length of both num1 and num2 is < 5100.\n",
    "* Both num1 and num2 contains only digits 0-9.\n",
    "* Both num1 and num2 does not contain any leading zero.\n",
    "* You must not use any built-in BigInteger library or convert the inputs to integer directly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We could convert the characters in num1 and num2 into ascii and calculate the difference with ascii of '0'. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def addStrings(self, num1, num2):\n",
    "        \"\"\"\n",
    "        :type num1: str\n",
    "        :type num2: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        n1=len(num1)\n",
    "        n2=len(num2)\n",
    "        result=[]\n",
    "        add=0\n",
    "        i=n1-1\n",
    "        j=n2-1\n",
    "        while i>=0 and j>=0:\n",
    "            digital_sum=add+ord(num1[i])+ord(num2[j])-2*ord('0')\n",
    "            if digital_sum>9:\n",
    "                digital_sum-=10\n",
    "                add=1\n",
    "            else:\n",
    "                add=0\n",
    "            result.append(digital_sum)\n",
    "            i-=1\n",
    "            j-=1\n",
    "        \n",
    "        while i>=0:\n",
    "            digital_sum=add+ord(num1[i])-ord('0')\n",
    "            if digital_sum>9:\n",
    "                digital_sum-=10\n",
    "                add=1\n",
    "            else:\n",
    "                add=0\n",
    "            result.append(digital_sum)\n",
    "            i-=1\n",
    "            \n",
    "        while j>=0:\n",
    "            digital_sum=add+ord(num2[j])-ord('0')\n",
    "            if digital_sum>9:\n",
    "                digital_sum-=10\n",
    "                add=1\n",
    "            else:\n",
    "                add=0\n",
    "            result.append(digital_sum)\n",
    "            j-=1\n",
    "            \n",
    "        if add==1:\n",
    "            result.append(add)\n",
    "            \n",
    "        return ''.join([str(num) for num in result[::-1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'100'"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.addStrings('99','1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=red>423. Reconstruct Original Digits from English(Not understanding the problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.\n",
    "\n",
    "Note:\n",
    "1. Input contains only lowercase English letters.\n",
    "2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as \"abc\" or \"zerone\" are not permitted.\n",
    "3. Input length is less than 50,000.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: \"owoztneoer\"\n",
    "\n",
    "Output: \"012\"\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: \"fviefuro\"\n",
    "\n",
    "Output: \"45\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def originalDigits(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 441. Arranging Coins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.\n",
    "\n",
    "Given n, find the total number of full staircase rows that can be formed.\n",
    "\n",
    "n is a non-negative integer and fits within the range of a 32-bit signed integer.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "n = 5\n",
    "\n",
    "The coins can form the following rows:\n",
    "\n",
    "¤\n",
    "\n",
    "¤ ¤\n",
    "\n",
    "¤ ¤\n",
    "\n",
    "Because the 3rd row is incomplete, we return 2.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "n = 8\n",
    "\n",
    "The coins can form the following rows:\n",
    "\n",
    "¤\n",
    "\n",
    "¤ ¤\n",
    "\n",
    "¤ ¤ ¤\n",
    "\n",
    "¤ ¤\n",
    "\n",
    "Because the 4th row is incomplete, we return 3.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We only need to compute the total number of coins up to kth row:\n",
    "\n",
    "k(k+1)/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def arrangeCoins(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n==0:\n",
    "            return 0\n",
    "        k=1\n",
    "        while (k+1)*(k+2)/2<2**31:\n",
    "            if n<(k+1)*(k+2)/2 and n>=k*(k+1)/2:\n",
    "                return k\n",
    "            k+=1\n",
    "            \n",
    "        return k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE. We could come up with O(sqrt(n)) solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def arrangeCoins(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n==0:\n",
    "            return 0\n",
    "        k=1\n",
    "        while k*(k+1)<=2*n:\n",
    "            k+=1\n",
    "            \n",
    "        return k-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "but still TLE. We could further improve the above algorithm by binary search: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def arrangeCoins(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        start=0\n",
    "        end=2*n\n",
    "        while start<=end:\n",
    "            mid=(start+end)/2\n",
    "            if mid*(mid+1)<2*n:\n",
    "                start=mid+1\n",
    "            elif mid*(mid+1)>2*n:\n",
    "                end=mid-1\n",
    "            else:\n",
    "                return mid\n",
    "            \n",
    "        return start-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "int(math.sqrt(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 453. Minimum Moves to Equal Array Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.\n",
    "\n",
    "Example:\n",
    "\n",
    "Input:\n",
    "[1,2,3]\n",
    "\n",
    "Output:\n",
    "3\n",
    "\n",
    "Explanation:\n",
    "\n",
    "Only three moves are needed (remember each move increments two elements):\n",
    "\n",
    "[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Minimum step=sum(maximum in the array-array[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def minMoves(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return sum(nums)-len(nums)*min(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is wrong for the case [1,1,2]. After every move, the total sum increase by n-1, while the minimum could increase by 1. The minimum number of moves should be \n",
    "$$\n",
    "n*(min+k)=sum+k*(n-1)\n",
    "=>k=sum-n*min\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It could be helpful to consider other solutions in understanding the problem:\n",
    "\n",
    "https://discuss.leetcode.com/topic/66759/four-python-solutions-with-detailed-explanation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 462. Minimum Moves to Equal Array Elements II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.\n",
    "\n",
    "You may assume the array's length is at most 10,000.\n",
    "\n",
    "Example:\n",
    "\n",
    "Input:\n",
    "[1,2,3]\n",
    "\n",
    "Output:\n",
    "2\n",
    "\n",
    "Explanation:\n",
    "Only two moves are needed (remember each move increments or decrements one element):\n",
    "\n",
    "[1,2,3]  =>  [2,2,3]  =>  [2,2,2]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Consider [1,2,3,7,8,9] 3+4+5+6=18 moves 4+5+6+1+2=18 \n",
    "\n",
    "[3,4,6] 2+1=3 moves\n",
    "\n",
    "So we need to find the median number and the minimum number of moves is to sum up the absolute difference."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def minMoves2(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        median=nums[n/2]\n",
    "        return sum([abs(nums[i]-median) for i in xrange(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1,2,7,9]\n",
    "o.minMoves2(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use quicksort algorithm to improve the running time to be O(n)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}