Binary Watch: Bit Counting Enumeration

LeetCode Binary Watch (Problem 401) gives you a binary watch with 10 LEDs: 4 for hours (representing 8, 4, 2, 1) and 6 for minutes (representing 32, 16, 8, 4, 2, 1). Given an integer turnedOn, you need to return all possible times the watch could display when exactly that many LEDs are lit.

The output should be a list of strings in the format "h:mm", where h has no leading zero and mm is always two digits.

The problem

You are given a non-negative integer turnedOn representing the number of LEDs currently on. Return all possible times the watch could represent.

• turnedOn = 1 returns times like ["0:01", "0:02", "0:04", "0:08", "0:16", "0:32", "1:00", "2:00", "4:00", "8:00"].
• turnedOn = 2 returns times like ["0:03", "0:05", "0:06", "0:09", "0:10", ...] plus mixed ones like ["1:01", "1:02", ...].

Hours range from 0 to 11. Minutes range from 0 to 59. Any combination exceeding those bounds is invalid.

Why bit counting works

Your first instinct might be to use backtracking: pick which LEDs to turn on from the 10 available, then split the chosen LEDs into hour and minute contributions, validate the time, and collect results. That works, but there is a much cleaner path.

Instead of choosing LEDs, just iterate every valid time directly. There are only 12 possible hours and 60 possible minutes. For each (hour, minute) pair, count the number of 1-bits in the binary representation of both values. If popcount(hour) + popcount(minute) equals turnedOn, that time is a valid answer.

This works because each LED maps to exactly one bit in either the hour or minute value. Turning on k LEDs total means exactly k bits are set across the two numbers combined. So checking the total bit count is equivalent to checking which LEDs are lit.

Step-by-step walkthrough

A few things to notice:

• The search space is tiny. 12 hours times 60 minutes is only 720 pairs. You can afford to check every single one.
• popcount (counting set bits) is the only operation you need. In Python, bin(n).count('1') does the job. In many languages, there is a built-in like Integer.bitCount() in Java or __builtin_popcount() in C++.
• The output naturally comes in sorted order if you iterate hours from 0 to 11 and minutes from 0 to 59 within each hour.

The code

def readBinaryWatch(turnedOn):
    result = []
    for h in range(12):
        for m in range(60):
            if bin(h).count('1') + bin(m).count('1') == turnedOn:
                result.append(f"{h}:{m:02d}")
    return result

The outer loop walks hours 0 through 11. The inner loop walks minutes 0 through 59. For each pair, you convert both to binary, count the 1-bits, and check the sum. The f"{h}:{m:02d}" format gives you no leading zero on the hour and a zero-padded two-digit minute, which is exactly what the problem requires.

Complexity analysis

The search space is always 12 * 60 = 720 pairs, regardless of the input. The loop runs a fixed number of iterations, popcount on small numbers is O(1), and the result list is bounded by 720 entries maximum. Both time and space are constant with respect to the input.

The building blocks

Bit counting as constraint checking

The core insight here is that you can encode a combinatorial constraint as a bit count. Instead of asking "which subset of 10 LEDs sums to this time?", you ask "does this time have the right number of set bits?" The two questions are equivalent, but the second one is much simpler to answer.

This pattern shows up in several other problems:

• Checking if a number is a power of two (exactly 1 bit set)
• Determining Hamming distance between two numbers (popcount of their XOR)
• Counting valid states in bitmask DP where you need a specific number of selected items

Edge cases

turnedOn = 0: Only one valid time: "0:00". Both hour and minute have zero set bits. The function returns ["0:00"].

turnedOn = 1: Returns 10 times. Each of the 10 LEDs (4 hour + 6 minute) individually produces a valid time.

Large turnedOn values: For turnedOn = 8 or higher, the maximum number of bits in valid times (hour up to 11 = 1011 = 3 bits, minute up to 59 = 111011 = 5 bits) is only 8 total. So turnedOn = 9 and turnedOn = 10 both return empty lists because no valid time has that many bits.

Hour overflow: Hour values above 11 are invalid. For example, 12 in binary is 1100 (2 bits), but since 12 is not a valid hour, no (12, m) pair is generated. The loop range range(12) handles this automatically.

Minute overflow: Similarly, minute values above 59 are invalid. 60 in binary is 111100 (4 bits). The loop range range(60) excludes it.

From understanding to recall

The key recall cue for this problem is: "720 pairs, count bits, check sum." If you can retrieve that sentence, the solution writes itself. You do not need to remember any backtracking tree structure or subset enumeration logic.

The reason this problem is a good drill target is that it reinforces the habit of checking whether brute force over a bounded space is sufficient before reaching for a more complex algorithm. Many bit manipulation problems have tiny search spaces, and the simplest approach is often the best one.

Practice this problem a few times from a blank editor. Each rep should take under two minutes once the pattern is locked in. Focus on getting the output format right on the first try, since that is the most common source of bugs.

Related posts

• Number of 1 Bits - counting set bits (Hamming weight) which is the core operation here
• Counting Bits - systematic bit counting across a range of numbers
• Power of Two - another bit manipulation problem with a clean mathematical solution

Bit counting turns a combinatorial search into a simple loop. Once you see that 720 candidates is trivially small and that popcount encodes the LED constraint exactly, the problem collapses to a few lines of code. Lock in the pattern, and you will recognize it instantly the next time a problem hands you a small bounded search space with a bitwise structure.