Code Implementation

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> list[str]:
        res = []
        for h in range(12):
            for m in range(60):
                if (bin(h).count('1') + bin(m).count('1')) == turnedOn:
                    res.append(f"{h}:{m:02d}")
        return res
      

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> res;
        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                    char buf[6];
                    sprintf(buf, "%d:%02d", h, m);
                    res.push_back(string(buf));
                }
            }
        }
        return res;
    }
};
      

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    res.add(String.format("%d:%02d", h, m));
                }
            }
        }
        return res;
    }
}
      

var readBinaryWatch = function(turnedOn) {
    let res = [];
    for (let h = 0; h < 12; h++) {
        for (let m = 0; m < 60; m++) {
            if ((h.toString(2).split('1').length - 1) + (m.toString(2).split('1').length - 1) === turnedOn) {
                res.push(h + ":" + (m < 10 ? "0" : "") + m);
            }
        }
    }
    return res;
};
      

Problem Description

You are given a binary watch, which displays the time using LEDs for hours and minutes. There are 4 LEDs for the hour (0-11) and 6 LEDs for the minutes (0-59). Each LED represents a binary digit (1 = on, 0 = off).

Given an integer turnedOn, representing the number of LEDs that are currently on, return all possible times the watch could represent. The answer can be returned in any order.

• Each valid time must be formatted as "H:MM", where H is hours (no leading zero), and MM is minutes (always two digits, zero-padded if needed).
• Do not reuse LEDs; each LED can only be on or off once.
• All returned times must be valid: hours in [0, 11], minutes in [0, 59].

Thought Process

At first glance, the problem appears to require generating all combinations of LEDs and mapping them to valid times. One naive approach is to try all possible ways to turn on turnedOn LEDs out of 10, then check which combinations correspond to valid times.

But instead of generating combinations, we can flip the problem: for each possible hour (0-11) and each possible minute (0-59), we can count how many LEDs would be on if the watch displayed that time. If the total number matches turnedOn, we include that time in the answer.

This approach is simple, direct, and avoids unnecessary complexity. It leverages the fact that the number of possible hour and minute values is small (12 * 60 = 720), so a brute-force enumeration is efficient.

Solution Approach

• Step 1: Loop through all possible hours (h) from 0 to 11.
• Step 2: For each hour, loop through all possible minutes (m) from 0 to 59.
• Step 3: For each pair (h, m), count the number of 1s in the binary representation of h and m. This represents how many LEDs are on for this time.
• Step 4: If the total number of LEDs on (bin(h).count('1') + bin(m).count('1')) equals turnedOn, this is a valid time. Format it as "H:MM" (hours without leading zero, minutes with two digits).
• Step 5: Collect all such times in a result list and return it.

This approach is justified because the total number of possible times is small, and checking each is very fast. We use functions like bin() or bitCount() for efficiency, since counting set bits is O(1) for small integers.

Example Walkthrough

Suppose turnedOn = 1. We want all times where exactly one LED is on.

• Loop through all hours (0-11) and minutes (0-59).
• For each time, count the number of 1s in hour and minute.
• For example, hour = 1 (binary 0001), minute = 0 (binary 000000): total = 1 + 0 = 1. So "1:00" is valid.
• hour = 0 (0000), minute = 1 (000001): total = 0 + 1 = 1. So "0:01" is valid.
• hour = 0, minute = 2 (000010): total = 0 + 1 = 1. So "0:02" is valid.
• Continue this way, collecting all hour/minute pairs where the total set bits is 1.
• Final output for turnedOn = 1 will be: ["0:01", "0:02", "0:04", "0:08", "0:16", "0:32", "1:00", "2:00", "4:00", "8:00"]

Time and Space Complexity

• Brute-force approach: Generating all 10-bit combinations and mapping to hour/minute is O(C(10, turnedOn)), but mapping to valid times is tricky and redundant.
• Optimized approach (used here): We check all 12 hours and 60 minutes, so 12 * 60 = 720 iterations. For each, counting bits is O(1) for small numbers.
  • Time Complexity: O(720) = O(1) (since 720 is constant and small)
  • Space Complexity: O(1) auxiliary, plus O(N) for the output list, where N is the number of valid times (at most 720)

Summary

The Binary Watch problem is elegantly solved by recognizing that the total number of possible times is small, making brute-force enumeration feasible and efficient. By looping through all valid hour and minute values, counting set bits, and formatting the result, we avoid unnecessary complexity and achieve a clean, direct solution. The key insight is to count set bits per time rather than generate all LED combinations.