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!