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:

0 <= hour <= 11

There are 6 LEDs for the minute.

The minute range is:

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

The hour has no leading zero.

The minute must always have two digits.

So:

1:05

is valid, but:

01:5

is not valid.

Examples

For:

turnedOn = 1

Only one LED is on.

Possible times include:

"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:

4:00

The hour 4 in binary is:

0100

So one hour LED is on.

The minute 0 in binary is:

000000

So no minute LED is on.

Total LEDs on:

1 + 0 = 1

First Thought: Generate LED Combinations

One way is to choose which LEDs are on.

There are 10 LEDs total:

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:

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:

hour

and:

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:

0 <= hour < 12

Loop through every valid minute:

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

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

Implementation

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:

ans = []

Then we enumerate every possible hour:

for hour in range(12):

This gives hours from 0 through 11.

For each hour, we enumerate every possible minute:

for minute in range(60):

This gives minutes from 0 through 59.

Then we count the number of turned-on LEDs:

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:

5.bit_count()

returns 2, because 5 is binary 101.

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

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

The format rule matters.

hour is printed normally.

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

So:

5

becomes:

05

Finally, we return all valid times:

return ans

Testing

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