Create binary-watch.py

kamyu104 · web-flow · commit b2fe8aae00a4 · 2016-09-18T18:00:06.000+08:00
diff --git a/Python/binary-watch.py b/Python/binary-watch.py
@@ -0,0 +1,38 @@
+# Time:  O(1)
+# Space: O(1)
+
+# 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.
+#
+# 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".
+
+
+class Solution(object):
+    def readBinaryWatch(self, num):
+        """
+        :type num: int
+        :rtype: List[str]
+        """
+        def bit_count(bits):
+            count = 0
+            while bits:
+                bits &= bits-1
+                count += 1
+            return count
+
+        return ['%d:%02d' % (h, m)
+            for h in xrange(12) for m in xrange(60)
+            if bit_count(h) + bit_count(m) == num]
