Binary Watch - Leetcode Solution

Problem Statement:

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.

Given an integer turnedOn which represents the number of LEDs that are currently on, 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 be consist of two digits and may contain a leading zero.

For example, "10:2" is not valid. It should be "10:02".

Input: turnedOn = 1 Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"] Explanation: We can turn on the following LEDs:

• Hour: 1
• Minute: None

Input: turnedOn = 9 Output: []

Approach:

The approach to solve this problem is to enumerate all the possible values of hours and minutes, such that the number of LEDs that are turned on in these values are equal to the given input turnedOn.

We can start by iterating over all possible values of the hours (0-11) and minutes (0-59), and for each value, count the number of set bits in the binary representation of the hour and minutes. If the sum of these counts is equal to turnedOn, then this value represents a valid time.

We can use the built-in "bin" function to obtain the binary representation of a number, and count the number of set bits using the "count" method of strings.

Code:

def readBinaryWatch(self, turnedOn: int) -> List[str]: res = [] for h in range(12): for m in range(60): if (bin(h) + bin(m)).count('1') == turnedOn: res.append('%d:%02d' % (h, m))

return res

Time Complexity:

The above code iterates over all possible values of hours and minutes, and counts the number of set bits in their binary representation. This takes O(1) time for each value, and there are a total of 12*60=720 possible values, so the time complexity of this approach is O(720).

Space Complexity:

The above code stores the valid times in a list, which takes O(k) space, where k is the total number of valid times. In the worst case, all possible values of hours and minutes have turnedOn LEDs turned on, so k can be as large as 720. Therefore, the space complexity of this approach is O(720).

1