# LeetCode 401: Binary Watch

## Problem Restatement

A binary watch uses LEDs to show time.

There are 4 LEDs for the hour.

The hour range is:

```python
0 <= hour <= 11
```

There are 6 LEDs for the minute.

The minute range is:

```python
0 <= minute <= 59
```

Each LED represents one binary bit. A bit with value `1` means the LED is on.

Given an integer `turnedOn`, return all possible valid times where exactly `turnedOn` LEDs are on.

The answer may be returned in any order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `turnedOn` |
| Output | A list of time strings |
| Hour range | `0` to `11` |
| Minute range | `0` to `59` |
| Format | `"H:MM"` |

The hour has no leading zero.

The minute must always have two digits.

So:

```python
1:05
```

is valid, but:

```python
01:5
```

is not valid.

## Examples

For:

```python
turnedOn = 1
```

Only one LED is on.

Possible times include:

```python
"1:00"
"2:00"
"4:00"
"8:00"
"0:01"
"0:02"
"0:04"
"0:08"
"0:16"
"0:32"
```

Each of these times uses exactly one binary `1`.

For example:

```python
4:00
```

The hour `4` in binary is:

```python
0100
```

So one hour LED is on.

The minute `0` in binary is:

```python
000000
```

So no minute LED is on.

Total LEDs on:

```python
1 + 0 = 1
```

## First Thought: Generate LED Combinations

One way is to choose which LEDs are on.

There are 10 LEDs total:

```python
4 hour LEDs + 6 minute LEDs = 10 LEDs
```

We could generate all combinations of `turnedOn` LEDs, compute the hour and minute, then keep only valid times.

This works, but it needs more bookkeeping.

There is a simpler way.

## Key Insight

There are only 12 possible hours and 60 possible minutes.

So there are only:

```python
12 * 60 = 720
```

possible valid times.

We can simply check every valid time.

For each pair `(hour, minute)`, count how many `1` bits appear in:

```python
hour
```

and:

```python
minute
```

If the total number of `1` bits equals `turnedOn`, then this time is part of the answer.

## Algorithm

Create an empty list `ans`.

Loop through every valid hour:

```python
0 <= hour < 12
```

Loop through every valid minute:

```python
0 <= minute < 60
```

For each time:

1. Count the number of `1` bits in `hour`.
2. Count the number of `1` bits in `minute`.
3. Add the two counts.
4. If the total equals `turnedOn`, format the time as `"H:MM"` and append it.

## Correctness

Every valid binary watch time must have an hour between `0` and `11` and a minute between `0` and `59`.

The algorithm checks every such pair.

For each checked pair, it computes exactly how many LEDs are on by counting the `1` bits in the hour and minute. This matches the watch definition, because each LED corresponds to one binary bit.

If the count equals `turnedOn`, the time satisfies the requirement and is added to the result.

If the count differs from `turnedOn`, the time cannot be represented with exactly that many LEDs, so it is skipped.

Because the algorithm checks all valid times and keeps exactly the times with the required number of lit LEDs, the returned list is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(12 * 60)` | We check every valid time |
| Space | `O(1)` extra | Apart from the output list |

Since `12 * 60 = 720`, this is effectively constant time.

## Implementation

```python
class Solution:
    def readBinaryWatch(self, turnedOn: int) -> list[str]:
        ans = []

        for hour in range(12):
            for minute in range(60):
                lights = hour.bit_count() + minute.bit_count()

                if lights == turnedOn:
                    ans.append(f"{hour}:{minute:02d}")

        return ans
```

## Code Explanation

We store valid times in:

```python
ans = []
```

Then we enumerate every possible hour:

```python
for hour in range(12):
```

This gives hours from `0` through `11`.

For each hour, we enumerate every possible minute:

```python
for minute in range(60):
```

This gives minutes from `0` through `59`.

Then we count the number of turned-on LEDs:

```python
lights = hour.bit_count() + minute.bit_count()
```

The method `bit_count()` returns the number of `1` bits in the binary representation of an integer.

For example:

```python
5.bit_count()
```

returns `2`, because `5` is binary `101`.

If the total number of lights matches `turnedOn`, we add the formatted time:

```python
ans.append(f"{hour}:{minute:02d}")
```

The format rule matters.

`hour` is printed normally.

`minute:02d` means the minute must use two digits.

So:

```python
5
```

becomes:

```python
05
```

Finally, we return all valid times:

```python
return ans
```

## Testing

```python
def test_binary_watch():
    s = Solution()

    assert sorted(s.readBinaryWatch(0)) == ["0:00"]

    assert sorted(s.readBinaryWatch(1)) == sorted([
        "1:00", "2:00", "4:00", "8:00",
        "0:01", "0:02", "0:04", "0:08", "0:16", "0:32",
    ])

    assert "3:00" in s.readBinaryWatch(2)
    assert "0:03" in s.readBinaryWatch(2)
    assert "10:00" in s.readBinaryWatch(2)

    assert all(
        0 <= int(t.split(":")[0]) <= 11 and
        0 <= int(t.split(":")[1]) <= 59
        for t in s.readBinaryWatch(5)
    )

    assert s.readBinaryWatch(11) == []

    print("all tests passed")
```

## Test Notes

| Test | Why |
|---|---|
| `turnedOn = 0` | Only `0:00` is possible |
| `turnedOn = 1` | Checks the sample-style simple case |
| `turnedOn = 2` | Checks hour-only, minute-only, and mixed binary values |
| `turnedOn = 5` | Checks that all returned times are valid |
| `turnedOn = 11` | No valid time can use 11 LEDs because the largest valid hour and minute do not turn on all 10 useful bits at once |