Leetcode 401. Binary Watch
Problem Explanation
A binary watch uses binary codes to present the hours and minutes. The watch is composed of a set of 10 LEDs, where specific set of LEDS light up to represent a specific hour and a specific minute. For this problem, the upper four LEDs are representing the hours from 0 to 11 and the bottom 6 LEDs are representing the minutes from 0 to 59. Each LED represents a binary representation, either 0 or 1, with the least significant bit on the right.
The task is to write a program that, given a non-negative integer n
which represents the number of LEDs that are currently on, it should bring back all possible times the watch could represent. The hour must not contain a leading zero, for example "01:00" is not acceptable. It should be "1:00". The minute must consist of two digits and may contain a leading zero.
Example
Input: n = 1
Output: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
In the above example, if there is only one LED is on, there will be a number of ways to represent the time. The hours could be 1,2,4,8 and minutes could be 01, 02, 04, 08, 16 and 32.
Solution Approach
The suggested solution is using a recursive Depth-First Search (DFS) to find all possibilities. For each LED that is switched on, we check if it can be added to the current time without exceeding the maximum hours (12) or minutes (59). If it can, we add this time to the list of possible times.
The constant time variables hours
and minutes
are defined with their possible maximum values in a binary structure, and for each LED, we check the current i
index, if it's less than 4 (which means it's an hour LED), it checks if adding the hour value won't exceed 12, if it doesn't, it recursively calls the dfs
function with the new value. The same process repeats for the minute LEDs, if the LED index i
is greater than 4, but it's using the minute variable instead.
This DFS approach ensures that all possible combinations of hours and minutes are covered.
Python Solution
1 2python 3class Solution: 4 def readBinaryWatch(self, num: int) -> List[str]: 5 hours = [1,2,4,8] 6 minutes = [1,2,4,8,16,32] 7 possible_times = [] 8 9 def explore(n, start, h, m): 10 # check if we reached the required count of LEDs 11 if n == 0: 12 # check if the minutes are less than 10, if so, add a leading zero 13 possible_times.append(f"{h}:{m:02d}") 14 return 15 # try each possible LED from the current starting point 16 for i in range(start, len(hours) + len(minutes)): 17 # if it's an hour LED, add it to the current hours 18 if i < len(hours) and h + hours[i] < 12: 19 explore(n - 1, i + 1, h + hours[i], m) 20 # if it's a minute LED, add it to the current minutes 21 elif i >= len(hours) and m + minutes[i - len(hours)] < 60: 22 explore(n - 1, i + 1, h, m + minutes[i - len(hours)]) 23 24 explore(num, 0, 0, 0) 25 return possible_times
Java Solution
1
2java
3class Solution {
4 int[] hours = new int[]{1,2,4,8};
5 int[] minutes = new int[]{1,2,4,8,16,32};
6 List<String> possibleTimes = new ArrayList<String>();
7
8 public List<String> readBinaryWatch(int num) {
9 explore(num, 0, 0, 0);
10 return possibleTimes;
11 }
12
13 private void explore(int num, int start, int hour, int minute) {
14 if(num == 0) {
15 possibleTimes.add(
16 String.format("%d:%02d", hour, minute));
17 return;
18 }
19 for(int i=start; i < hours.length + minutes.length; ++i) {
20 if(i < hours.length && hour + hours[i] < 12)
21 explore(num - 1, i + 1, hour + hours[i], minute);
22 else if(i >= hours.length && minute + minutes[i - hours.length] < 60)
23 explore(num - 1, i + 1, hour, minute + minutes[i - hours.length]);
24 }
25 }
26
27}
JavaScript Solution
1
2js
3var readBinaryWatch = function(num) {
4 let hours = [1, 2, 4, 8];
5 let minutes = [1, 2, 4, 8, 16, 32];
6 let possibleTimes = [];
7
8 function explore(n, start, h, m) {
9 if(n == 0) {
10 possibleTimes.push(`${h}:${m.toString().padStart(2,'0')}`);
11 return;
12 }
13 for(let i=start; i < hours.length + minutes.length; i++) {
14 if(i < hours.length && h + hours[i] < 12)
15 explore(n - 1, i + 1, h + hours[i], m);
16 else if(i >= hours.length && m + minutes[i - hours.length] < 60)
17 explore(n - 1, i + 1, h, m + minutes[i - hours.length]);
18 }
19 }
20
21 explore(num, 0, 0, 0);
22 return possibleTimes;
23};
C++ Solution
1
2cpp
3class Solution {
4public:
5 vector<string> readBinaryWatch(int num) {
6 vector<string> ans;
7 auto hours = vector<int>{1, 2, 4, 8};
8 auto minutes = vector<int>{1, 2, 4, 8, 16, 32};
9 explore(num, 0, 0, 0, ans, hours, minutes);
10 return ans;
11 }
12
13private:
14 void explore(int n, int s, int h, int m, vector<string>& ans, const vector<int>& hours,
15 const vector<int>& minutes) const {
16 if (n == 0) {
17 string time = to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m);
18 ans.push_back(time);
19 return;
20 }
21
22 for (int i = s; i < hours.size() + minutes.size(); ++i)
23 if (i < 4 && h + hours[i] < 12)
24 explore(n - 1, i + 1, h + hours[i], m, ans, hours, minutes);
25 else if (i >= 4 && m + minutes[i - 4] < 60)
26 explore(n - 1, i + 1, h, m + minutes[i - 4], ans, hours, minutes);
27 }
28};
Summary
Binary watches provide a perfect use case for exploring the concepts of binary representations and recursive Depth-First Search. In the defined problem, we are given a non-negative integer representing the number of LEDS that are currently lit up and have to find all possible times the watch could represent given the condition.
A solution to this problem requires a comprehension of binary representations and a good understanding on how to implement a recursive algorithm.
The process involves creating a recursive function to search for all possible combinations of hours and minutes. Each LED is checked if itโs for an hour or a minute, ensuring it doesn't exceed the allowable maximum. Once a valid combination is found, it's added to the list of possible times.
This process is conducted with a DFS approach, assuring all possible combinations are covered before punching out an output list of possible times. The coding implementation of this solution was shown using Python, Java, JavaScript and C++ languages.
For beginners or someone who is learning to code, experimenting with such a problem could be a great way to practice recursive problems and to understand an application of the binary counting. Happy coding!
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.