401. Binary Watch

Description

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

• For example, the below binary watch reads "4:51".
  
  Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.
  The hour must not contain a leading zero.
• For example, "01:00" is not valid. It should be "1:00".
  The minute must consist of two digits and may contain a leading zero.
• For example, "10:2" is not valid. It should be "10:02".

Example 1:

• Input: turnedOn = 1
• Output: [“0:01”,”0:02”,”0:04”,”0:08”,”0:16”,”0:32”,”1:00”,”2:00”,”4:00”,”8:00”]

Example 2:

• Input: turnedOn = 9
• Output: []

Constraints:

• 0 <= turnedOn <= 10

💡 Hint 1:
Simplify by seeking for solutions that involve comparing bit counts.
💡 Hint 2:
Consider calculating all possible times for comparison purposes.

Submitted Code

class Solution(object):
    def readBinaryWatch(self, turnedOn):
        """
        :type turnedOn: int
        :rtype: List[str]
        """
        result = []
        for h in range(12):         # hour: 0~11
            for m in range(60):     # minute: 0~59
                if bin(h).count('1') + bin(m).count('1') == turnedOn:
                    result.append("{}:{:02d}".format(h, m))
        return result

Runtime: 0 ms | Beats 100.00%
Memory: 12.30 MB | Beats 99.00%

가능한 모든 시간을 이진수로 바꾸면 1의 개수가 전체 LED 중 켜진 개수가 된다.

Other Solutions

1st

from itertools import combinations

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        # ignore input greater than 8
        if turnedOn >= 9:
            return []

        res = []
        # Iterate over all combinations
        for shift_factors in combinations(range(10), turnedOn):
            
            # Reconstruct time, O(n)
            time = 0
            for i in shift_factors:
                time |= 1 << i
            h = time & 0b1111
            m = time >> 4
            
            # Validate time
            if h <= 11 and m <= 59:
                res.append(f'{h}:{m:02}')

        return res

time complexity: 𝑂(𝑘 * 10/𝑘) ← 𝑘 = turnedOn
space complexity: 𝑂(1)

전체 720개의 시간(12 * 60)를 순회하지 않기 때문에 좀 더 최적화된 비트 조합 기반 방법이다. 파이썬 표준 모듈 itertools의 함수 combinations는 n개 중에서 r개를 뽑는 모든 조합을 생성한다. 이 경우 인덱스 10개(0-9) 중에서 turnedOn개를 고르는 모든 조합이다.

shift_factors = [1, 4] (조합 예시 중 1)
time = (0b)0000000000

                ↓         ↓
[9][8][7][6][5][4] [3][2][1][0]
 m  m  m  m  m  m   h  h  h  h

i = 1
0000000000 | 0000000010(1 << 1) = 0000000010(time)
↓
i = 4
0000000010 | 0000010000(1 << 4) = 0000010010(time)
↓
time에서 h 추출
0000010010 & 0000001111 = 0000000010 = 2
↓
time에서 m 추출
0000010010 >> 4         = 0000000001 = 1

res.append(“2:01”)