401. Binary Watch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).\n",
    "\n",
    "Each LED represents a zero or one, with the least significant bit on the right.\n",
    "For example, the above binary watch reads \"3:25\".\n",
    "\n",
    "Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.\n",
    "\n",
    "Example:\n",
    "\n",
    "Input: n = 1\n",
    "Return: [\"1:00\", \"2:00\", \"4:00\", \"8:00\", \"0:01\", \"0:02\", \"0:04\", \"0:08\", \"0:16\", \"0:32\"]\n",
    "Note:\n",
    "The order of output does not matter.\n",
    "The hour must not contain a leading zero, for example \"01:00\" is not valid, it should be \"1:00\".\n",
    "The minute must be consist of two digits and may contain a leading zero, for example \"10:2\" is not valid, it should be \"10:02\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def readBinaryWatch(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if num==0:\n",
    "            return [\"0:00\"]\n",
    "        \n",
    "        self.ref=[1,2,4,8,1,2,4,8,16,32]\n",
    "        \n",
    "        self.res=[]\n",
    "        self.dfs(0,0,0,num)\n",
    "        return self.res\n",
    "        \n",
    "    def dfs(self,start,hour,minute,n):\n",
    "        if hour>=12 or minute>59:\n",
    "            return\n",
    "        if n==0:\n",
    "            \n",
    "            self.res.append(str(hour)+\":\"+\"0\"*(minute<10)+str(minute))\n",
    "            return\n",
    "        \n",
    "        for i in range(start,10):\n",
    "            if i<4:\n",
    "                self.dfs(i+1,hour+self.ref[i],minute,n-1)\n",
    "            else:\n",
    "                self.dfs(i+1,hour,minute+self.ref[i],n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "s=Solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['3:00',\n",
       " '5:00',\n",
       " '9:00',\n",
       " '1:01',\n",
       " '1:02',\n",
       " '1:04',\n",
       " '1:08',\n",
       " '1:16',\n",
       " '1:32',\n",
       " '6:00',\n",
       " '10:00',\n",
       " '2:01',\n",
       " '2:02',\n",
       " '2:04',\n",
       " '2:08',\n",
       " '2:16',\n",
       " '2:32',\n",
       " '4:01',\n",
       " '4:02',\n",
       " '4:04',\n",
       " '4:08',\n",
       " '4:16',\n",
       " '4:32',\n",
       " '8:01',\n",
       " '8:02',\n",
       " '8:04',\n",
       " '8:08',\n",
       " '8:16',\n",
       " '8:32',\n",
       " '0:03',\n",
       " '0:05',\n",
       " '0:09',\n",
       " '0:17',\n",
       " '0:33',\n",
       " '0:06',\n",
       " '0:10',\n",
       " '0:18',\n",
       " '0:34',\n",
       " '0:12',\n",
       " '0:20',\n",
       " '0:36',\n",
       " '0:24',\n",
       " '0:40',\n",
       " '0:48']"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.readBinaryWatch(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "str"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(bin(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b1001'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(bin(10)+bin(9)).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def readBinaryWatch(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if num==0:\n",
    "            return [\"0:00\"]\n",
    "        res=[]\n",
    "        for h in range(12):\n",
    "            for m in range(59):\n",
    "                if (bin(h)+bin(m)).count('1')==num:\n",
    "                    res.append(\"%d:%02d\"%(h,m))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "a=8\n",
    "b=17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8:17\n"
     ]
    }
   ],
   "source": [
    "print(\"%d:%02d\"%(a,b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}