Binary Watch

• Initialize an empty list result to store the valid times.
• Loop for hour h from 0 to 11.
• Inside the hour loop, loop for minute m from 0 to 59.
• Calculate the number of set bits for the current hour h and minute m using Integer.bitCount(h) + Integer.bitCount(m).
• If the total number of set bits equals turnedOn:
  • Format the time as a string h:mm. The minute part must be two digits, so pad with a leading zero if necessary (e.g., 7 becomes 07).
  • Add the formatted string to the result list.
• After the loops complete, return the result list.

The most straightforward way to solve this problem is to simulate a clock and check every minute of a 12-hour cycle. We can use nested loops to iterate through all possible hours (h) from 0 to 11 and all possible minutes (m) from 0 to 59.

In each iteration, we need to determine how many LEDs would be on for that specific time h:m. This is equivalent to counting the number of set bits (1s) in the binary representations of h and m. Most programming languages provide a built-in function for this, such as Integer.bitCount() in Java.

The total number of 'on' LEDs is the sum of bits for the hour and the minute: Integer.bitCount(h) + Integer.bitCount(m).

We compare this sum with the input turnedOn. If they are equal, we have found a valid time. We then format this time into the required "H:MM" string format. For example, if h=4 and m=5, the string should be "4:05". This formatted string is then added to our list of results.

After checking all 12 * 60 = 720 possible times, the list containing all valid time strings is returned.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<String> readBinaryWatch(int turnedOn) {6        List<String> result = new ArrayList<>();7        // Iterate through all possible hours (0-11)8        for (int h = 0; h < 12; h++) {9            // Iterate through all possible minutes (0-59)10            for (int m = 0; m < 60; m++) {11                // Count the number of set bits for hour and minute12                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {13                    // Format the time and add to the result list14                    result.add(String.format("%d:%02d", h, m));15                }16            }17        }18        return result;19    }20}

• Initialize an empty list result.
• Loop for h_leds (number of hour LEDs) from 0 to turnedOn.
• Calculate m_leds = turnedOn - h_leds.
• If h_leds > 4 or m_leds > 6, it's an invalid distribution, so skip to the next iteration.
• Generate a list hours containing all integers from 0-11 that have exactly h_leds set bits.
• Generate a list minutes containing all integers from 0-59 that have exactly m_leds set bits.
• Use nested loops to iterate through each h in hours and each m in minutes.
• For each pair (h, m), format the time as a string h:mm and add it to result.
• Return result.

A more efficient method is to think about the problem in terms of combinations. We have a total of turnedOn LEDs to distribute among the 4 hour LEDs and 6 minute LEDs.

Let h_leds be the number of LEDs turned on for the hour and m_leds be the number for the minute. We know that h_leds + m_leds = turnedOn. We can iterate through all possible values for h_leds (from 0 up to turnedOn). For each h_leds, m_leds is determined.

We must respect the physical constraints of the watch: 0 <= h_leds <= 4 and 0 <= m_leds <= 6. So, for each h_leds we consider, we first check if this distribution is possible.

If the distribution is valid, we perform two sub-tasks:

1. Find all possible hour values (from 0 to 11) that can be formed with exactly h_leds LEDs on.
2. Find all possible minute values (from 0 to 59) that can be formed with exactly m_leds LEDs on.

We can generate these lists of hours and minutes by iterating from 0-11 and 0-59 respectively, and checking their bit counts. Once we have the list of possible hours and the list of possible minutes, we find their Cartesian product. Every hour from the first list is combined with every minute from the second list to form a valid time. Each resulting time is formatted and added to our final list.

This method significantly reduces the number of combinations to check compared to the brute-force approach, as it directly constructs valid possibilities rather than searching for them in a large space.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<String> readBinaryWatch(int turnedOn) {6        List<String> result = new ArrayList<>();7        // Iterate through all possible numbers of LEDs for the hour part (0 to 4)8        for (int h_leds = 0; h_leds <= 4; h_leds++) {9            // The remaining LEDs are for the minute part (0 to 6)10            int m_leds = turnedOn - h_leds;11            if (m_leds >= 0 && m_leds <= 6) {12                // Generate possible hours13                List<Integer> hours = new ArrayList<>();14                for (int h = 0; h < 12; h++) {15                    if (Integer.bitCount(h) == h_leds) {16                        hours.add(h);17                    }18                }19 20                // Generate possible minutes21                List<Integer> minutes = new ArrayList<>();22                for (int m = 0; m < 60; m++) {23                    if (Integer.bitCount(m) == m_leds) {24                        minutes.add(m);25                    }26                }27 28                // Combine hours and minutes to form times29                for (int h : hours) {30                    for (int m : minutes) {31                        result.add(String.format("%d:%02d", h, m));32                    }33                }34            }35        }36        return result;37    }38}