520_math.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 728. Self Dividing Numbers\n",
    "\n",
    "A self-dividing number is a number that is divisible by every digit it contains.\n",
    "\n",
    "For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.\n",
    "\n",
    "Also, a self-dividing number is not allowed to contain the digit zero.\n",
    "\n",
    "Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def selfDividingNumbers(self, left, right):\n",
    "        \"\"\"\n",
    "        :type left: int\n",
    "        :type right: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        r = []\n",
    "        def check(num, n):\n",
    "            v = n % 10 \n",
    "            if v == 0:\n",
    "                return False\n",
    "            else:\n",
    "                if num % v != 0:\n",
    "                    return False\n",
    "            if int(n/10) == 0:\n",
    "                return True\n",
    "            else:\n",
    "                return check(num, int(n/10))\n",
    "        for i in range(left, right+1):\n",
    "            if check(i, i):\n",
    "                r.append(i)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Advanced Version\n",
    "class Solution:\n",
    "    def selfDividingNumbers(self, left, right):\n",
    "        \"\"\"\n",
    "        :type left: int\n",
    "        :type right: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        v = []\n",
    "        for i in range(left,right+1):\n",
    "            k=i\n",
    "            flag=1\n",
    "            while k!=0:\n",
    "                val = k%10\n",
    "                if val!=0 and i%val==0:\n",
    "                    flag=1\n",
    "                else:\n",
    "                    flag=0\n",
    "                    break\n",
    "                k//=10\n",
    "            if(flag==1):\n",
    "                v.append(i)\n",
    "        return v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 202. Happy Number\n",
    "\n",
    "Write an algorithm to determine if a number is \"happy\".\n",
    "\n",
    "A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def partial_sum(n, ps):\n",
    "            ps += (n%10)**2\n",
    "            if int(n/10) == 0:\n",
    "                return ps\n",
    "            else:\n",
    "                return partial_sum(int(n/10), ps)\n",
    "        def check(n, s):\n",
    "            new = partial_sum(n, 0)\n",
    "            if new == 1:\n",
    "                return True\n",
    "            elif new in s:\n",
    "                return False\n",
    "            else:\n",
    "                s.add(new)\n",
    "                return check(new, s)\n",
    "        return check(n, set([]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### advanced\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        former = set()\n",
    "        while True:\n",
    "            h = 0\n",
    "            while n > 0:\n",
    "                d = n % 10\n",
    "                h += (d*d)\n",
    "                n = n // 10\n",
    "            if h == 1:\n",
    "                return True\n",
    "            elif h in former:\n",
    "                return False\n",
    "            n = h\n",
    "            former.add(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 258. Add Digits (***)\n",
    "\n",
    "Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.\n",
    "\n",
    "#### Digital Root: https://en.wikipedia.org/wiki/Digital_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def addDigits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return num - int((num-1)/9)*9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# advanced\n",
    "class Solution:\n",
    "    def addDigits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        return 1 + (num - 1) % 9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 231. Power of Two\n",
    "\n",
    "Given an integer, write a function to determine if it is a power of two."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def check(n):\n",
    "            if n == 1:\n",
    "                return True\n",
    "            elif n == 0:\n",
    "                return False\n",
    "            else:\n",
    "                if n % 2 != 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    return check(int(n/2))\n",
    "        return check(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if n < 0:\n",
    "            return False\n",
    "        \n",
    "        hasOne = False\n",
    "        while n > 0:\n",
    "            if n & 1:\n",
    "                if hasOne == True:\n",
    "                    return False\n",
    "                else:\n",
    "                    hasOne = True\n",
    "                    \n",
    "            n = n >> 1\n",
    "        \n",
    "        return hasOne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 645. Set Mismatch\n",
    "\n",
    "The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.\n",
    "\n",
    "Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### not good \n",
    "class Solution:\n",
    "    def findErrorNums(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                break\n",
    "        return [nums[i], sum(range(1, len(nums)+1)) - sum(set(nums))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# advanced version\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        scur = sum(nums)\n",
    "        sall = sum(range(1, len(nums) + 1))\n",
    "        sset = sum(set(nums))\n",
    "        return [scur - sset, sall - sset]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 67. Add Binary\n",
    "\n",
    "Given two binary strings, return their sum (also a binary string).\n",
    "\n",
    "The input strings are both non-empty and contains only characters 1 or 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        k = min(len(a), len(b))\n",
    "        string = ''\n",
    "        flag = 0\n",
    "        for i in range(-1, -k-1, -1):\n",
    "            if int(a[i]) + int(b[i]) + flag == 0:\n",
    "                string += '0' \n",
    "                flag = 0\n",
    "            elif int(a[i]) + int(b[i]) + flag == 1:\n",
    "                string += '1'\n",
    "                flag = 0\n",
    "            elif int(a[i]) + int(b[i]) + flag == 2:\n",
    "                string += '0'\n",
    "                flag = 1\n",
    "            else:\n",
    "                string += '1'\n",
    "                flag = 1\n",
    "                \n",
    "        def add(s, string, flag):\n",
    "            for i in range(-k-1, -len(s)-1, -1):\n",
    "                if int(s[i]) + flag == 0:\n",
    "                    string += '0'\n",
    "                    flag = 0\n",
    "                elif int(s[i]) + flag == 1:\n",
    "                    string += '1'\n",
    "                    flag = 0\n",
    "                else: \n",
    "                    string += '0'\n",
    "                    flag = 1\n",
    "            if flag == 1:\n",
    "                string += '1'\n",
    "            return string\n",
    "        \n",
    "        if k == len(a):  # a is shorter\n",
    "            string = add(b, string, flag)\n",
    "        else:\n",
    "            string = add(a, string, flag)\n",
    "        n = len(string)\n",
    "        r = ''\n",
    "        for i in range(n-1, -1, -1):\n",
    "            r += string[i]\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# advanced\n",
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        output=bin(int(a,2)+int(b,2))\n",
    "        return output[2:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 441. Arranging Coins\n",
    "\n",
    "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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# perfect\n",
    "import math\n",
    "def arrangeCoins(n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x = int((-1 + math.sqrt(1+8*n))/2)\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 400. Nth Digit (**)\n",
    "\n",
    "Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def findNthDigit(n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n < 10:\n",
    "            return n\n",
    "        count = 0\n",
    "        for i in range(20):\n",
    "            t1 = 9 * 10 ** i\n",
    "            t2 = 9 * 10 ** (i+1)\n",
    "            count = count + t1 * (i+1)\n",
    "            if (count < n) & (count + t2 * (i+2) >=n):\n",
    "                si = i\n",
    "                break\n",
    "        \n",
    "        t1 = int((n-count) / (i+2))\n",
    "        t2 = (n-count) % (i+2)\n",
    "        \n",
    "        if t2 == 0:\n",
    "            num1 = 10 ** (i+1) + t1 -1\n",
    "            return int(str(num1)[-1])\n",
    "        else:\n",
    "            num1 = 10 ** (i + 1) + t1\n",
    "            return int(str(num1)[t2-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "# advanced\n",
    "class Solution:\n",
    "    def findNthDigit(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        i=count=9\n",
    "        while count < n:\n",
    "            i *= 10\n",
    "            count += i * len(str(i))\n",
    "        div, mod = divmod(n-(count-i*len(str(i))), len(str(i)))\n",
    "        print(i, count, div, mod)\n",
    "        target = (i//9-1) + div\n",
    "        if mod == 0:\n",
    "            print(target, int(str(target)[-1]))\n",
    "            return int(str(target)[-1])\n",
    "        else:\n",
    "            return int(str(target+1)[mod-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 69. Sqrt(x)\n",
    "\n",
    "Implement int sqrt(int x).\n",
    "\n",
    "Compute and return the square root of x, where x is guaranteed to be a non-negative integer.\n",
    "\n",
    "Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "## poor\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c):\n",
    "        \"\"\"\n",
    "        :type c: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        for i in range(int(math.sqrt(c))+1):\n",
    "            if c - int(math.sqrt(c - i**2))**2 - i**2== 0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# advanced\n",
    "from math import sqrt\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c):\n",
    "        \"\"\"\n",
    "        :type c: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        i = 2\n",
    "        while i**2 <= c:\n",
    "            count = 0\n",
    "            if c % i == 0:\n",
    "                while c % i == 0:\n",
    "                    count, c = count + 1, c // i\n",
    "                if i % 4 == 3 and count % 2 != 0:\n",
    "                    return False\n",
    "            i += 1\n",
    "        return c % 4 != 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Analysis\n",
    "https://leetcode.com/problems/sum-of-square-numbers/solution/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}