myleetcode/binaryWatch.py at master · sfeng77/myleetcode · GitHub

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
"""
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.

https://upload.wikimedia.org/wikipedia/commons/8/8b/Binary_clock_samui_moon.jpg

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:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

    The order of output does not matter.
    The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
    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".

"""

class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        def generateBinary(num, bits):
            return [i for i in range(2 ** bits) if bin(i).count('1') == num]

        time = []
        for hourBits in range(num + 1):
            minuteBits = num - hourBits
            hour = generateBinary(hourBits, 4)
            minute = generateBinary(minuteBits, 6)
            for h in hour:
                if h > 11:
                    continue
                for m in minute:
                    if m > 59:
                        continue
                    s = str(h) + ":"
                    if m < 10:
                        s = s + "0" + str(m)
                    else:
                        s += str(m)
                    time.append(s)
        return time