Title: Binary Watch Source: leetcode.com
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).
Each LED represents a zero or one, with the least significant bit on the right.
A Binary Watch reading time: “3:25”.
For example, the above binary watch reads “3:25”.
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example 1:
Input: n=1
Output: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]
Solution
First thing to note about the problem is about the possible values we can have for n.
If we see the hours section of Watch, we have 4 LEDs. However, we can’t have all 4 in ON state simultaneously as it would make hour value to be more than 12 while the problem specifies hour values to be only in range 0-11.
Similarly, for minutes, we can’t have a value more than 59.
Next we need to have a way of making combinations similar to nCr (Choosing r values out of given n).
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
''' https://leetcode.com/problems/binary-watch/ ''' class Solution(object): def combination(self, n, k, inp, res): # inp is expected to be a list of size n #print n,k,inp,res if k == 0: res.append([i for i in inp]) return if k > n: return #for i in range(1,n+1): inp[n-1] = 1 self.combination(n-1,k-1, inp, res) inp[n-1] = 0 self.combination(n-1, k, inp, res) def getHours(self, h): if h == 0: return ["0"] if h == 1: return ["1", "2", "4", "8"] if h == 2: return ["3", "5", "6", "9", "10"] if h == 3: return ["7", "11"] def getMinutes(self, m): inp = [0,0,0,0,0,0] res = [] self.combination(6, m, inp, res) mins = [1, 2, 4, 8, 16, 32] minutes = [] for comb in res: i = 0 mn = 0 while i < 6: if comb[i] == 1: mn += mins[i] i += 1 if mn > 59: continue if mn < 10: minutes.append("0" + str(mn)) else: minutes.append(str(mn)) return minutes def readBinaryWatch(self, num): """ :type num: int :rtype: List[str] """ i = 0 res = [] while i <= num: h = i m = num - i if h < 4 and m < 6: lh = self.getHours(h) #print lh lm = self.getMinutes(m) #print lm for hr in lh: for mn in lm: res.append(hr + ":" + mn) i += 1 return res |