LeetCode 401 - Binary Watch

LeetCode Problem 401

Difficulty: 🟢 Easy
Topics: Backtracking, Bit Manipulation

Solution

Problem Understanding

The problem describes a binary watch that uses LEDs to represent time. The watch has two sections. The top section contains 4 LEDs for the hour, and the bottom section contains 6 LEDs for the minutes.

Each LED represents a binary digit. If an LED is on, it contributes its corresponding binary value. The hour LEDs can represent values from 0 to 11, while the minute LEDs can represent values from 0 to 59.

The input, turnedOn, tells us exactly how many LEDs are currently lit. Our task is to generate every valid time that can be represented using exactly that many active LEDs.

For example, if turnedOn = 1, then exactly one LED is on. That means valid times include values such as:

• "1:00" because one hour LED is active
• "0:01" because one minute LED is active
• "0:32" because the highest minute LED is active

The output should contain all valid times in any order.

There are important formatting rules for the generated times:

• Hours must not have leading zeros. "1:00" is valid, but "01:00" is not.
• Minutes must always contain exactly two digits. "10:02" is valid, but "10:2" is not.

The constraints are very small:

• 0 <= turnedOn <= 10

This tells us the total number of LEDs is fixed at 10, which means the search space is extremely limited. Even brute force solutions are feasible because there are only:

• 12 possible hours
• 60 possible minutes

That gives only 12 × 60 = 720 total possible times.

Several edge cases are important:

• turnedOn = 0, only "0:00" is valid.
• turnedOn = 9 or 10, no valid time may exist because valid hours and minutes cannot use that many LEDs simultaneously.
• Minute formatting must always preserve two digits.
• Hours must remain within 0-11.
• Minutes must remain within 0-59.

Approaches

Brute Force Approach

The brute force solution checks every possible valid time on the watch. Since hours range from 0 to 11 and minutes range from 0 to 59, we can iterate through all 720 possible combinations.

For each (hour, minute) pair, we count the number of set bits in both values. A set bit represents an LED that is turned on. If the total number of set bits equals turnedOn, then that time is added to the answer.

This approach is correct because it exhaustively checks every valid time configuration. No valid answer can be missed, and no invalid answer is included because we explicitly verify the LED count.

Although this is technically brute force, the input size is so small that it performs extremely well in practice.

Optimal Approach

The key insight is that the problem fundamentally depends on counting binary set bits.

Each LED corresponds directly to a binary 1. Therefore:

• The number of active LEDs for the hour equals the number of 1 bits in the hour value.
• The number of active LEDs for the minute equals the number of 1 bits in the minute value.

Instead of simulating LED positions explicitly with backtracking, we can directly leverage bit manipulation. We iterate through all valid times and use a bit-counting operation to determine whether the total number of active bits matches turnedOn.

This solution is optimal because:

• The total search space is fixed and tiny.
• Bit counting is extremely fast.
• The implementation is simple and easy to verify.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(720 × B)	O(1) excluding output	Checks every valid time and manually counts bits
Optimal	O(720)	O(1) excluding output	Uses efficient bit counting with bit manipulation

Here, B represents the number of bits examined during manual counting, which is at most 10.

Algorithm Walkthrough

1. Initialize an empty result list that will store all valid time strings.

2. Iterate through every possible hour from 0 to 11. These are the only valid hour values for the binary watch.

3. For each hour, iterate through every possible minute from 0 to 59. These are the only valid minute values.

4. Count the number of set bits in the hour value. Each set bit corresponds to one illuminated hour LED.

5. Count the number of set bits in the minute value. Each set bit corresponds to one illuminated minute LED.

6. Add the two counts together. This gives the total number of LEDs currently turned on for that time.

7. Compare the total count with turnedOn. If they match, then this is a valid time representation.

8. Format the time correctly before adding it to the result:

9. The hour is converted normally without leading zeros.

10. The minute is formatted with exactly two digits using zero-padding.

11. Continue until all 720 possible times have been checked.

12. Return the completed result list.

Why it works

The algorithm works because every valid watch state corresponds uniquely to a pair (hour, minute). By iterating through all valid hour and minute combinations, we guarantee that every possible watch configuration is examined exactly once.

The number of illuminated LEDs is exactly equal to the number of binary 1 bits in the hour and minute values combined. Therefore, selecting all times whose total set bit count equals turnedOn precisely matches the problem definition.

Python Solution

from typing import List

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        result = []

        for hour in range(12):
            for minute in range(60):
                led_count = bin(hour).count("1") + bin(minute).count("1")

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

        return result

The implementation begins by creating an empty list called result to store all valid times.

The outer loop iterates through every valid hour from 0 to 11, while the inner loop iterates through every valid minute from 0 to 59.

For each time combination, the code calculates the total number of active LEDs. This is done using Python's binary string representation:

bin(value).count("1")

The bin() function converts a number into binary form, and count("1") counts how many bits are set.

If the total LED count matches turnedOn, the time is formatted and appended to the result list. The expression:

f"{hour}:{minute:02d}"

ensures that minutes always contain two digits. For example:

• 5 becomes "05"
• 0 becomes "00"

Finally, the completed list is returned.

Go Solution

package main

import (
	"fmt"
	"math/bits"
)

func readBinaryWatch(turnedOn int) []string {
	result := []string{}

	for hour := 0; hour < 12; hour++ {
		for minute := 0; minute < 60; minute++ {
			ledCount := bits.OnesCount(uint(hour)) +
				bits.OnesCount(uint(minute))

			if ledCount == turnedOn {
				timeString := fmt.Sprintf("%d:%02d", hour, minute)
				result = append(result, timeString)
			}
		}
	}

	return result
}

The Go solution follows the same logic as the Python implementation, but it uses Go's standard library function:

bits.OnesCount()

This efficiently counts the number of set bits in an integer.

Slices are used to store the result dynamically. Unlike Python lists, Go slices require explicit appending using append().

Formatting is handled with:

fmt.Sprintf("%d:%02d", hour, minute)

which ensures the minute portion always has two digits.

There are no integer overflow concerns because all values remain very small.

Worked Examples

Example 1

Input: turnedOn = 1

We search for all times where exactly one LED is active.

Hour	Minute	Hour Bits	Minute Bits	Total LEDs	Valid
0	1	0	1	1	Yes
0	2	0	1	1	Yes
0	4	0	1	1	Yes
0	8	0	1	1	Yes
0	16	0	1	1	Yes
0	32	0	1	1	Yes
1	0	1	0	1	Yes
2	0	1	0	1	Yes
4	0	1	0	1	Yes
8	0	1	0	1	Yes

Final output:

["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Example 2

Input: turnedOn = 9

To satisfy this input, the total number of active LEDs must equal 9.

However:

• The maximum valid hour is 11, which has only 3 set bits.
• The maximum valid minute is 59, which has 5 set bits.

Maximum possible LEDs:

3 + 5 = 8

Since no valid time can activate 9 LEDs, the result is empty.

Hour	Minute	Max LEDs
11	59	8

Final output:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(720)	Checks all 12 × 60 possible times
Space	O(1) excluding output	Only a few variables are used

The algorithm always examines exactly 720 possible times, regardless of input. Since this number is constant, the runtime is effectively constant.

The auxiliary memory usage is also constant because the algorithm only stores loop variables and temporary counters. The returned result list is not included in auxiliary space complexity analysis.

Test Cases

from typing import List

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        result = []

        for hour in range(12):
            for minute in range(60):
                led_count = bin(hour).count("1") + bin(minute).count("1")

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

        return result

solution = Solution()

# Example 1
assert sorted(solution.readBinaryWatch(1)) == sorted([
    "0:01", "0:02", "0:04", "0:08",
    "0:16", "0:32",
    "1:00", "2:00", "4:00", "8:00"
])  # single LED active

# Example 2
assert solution.readBinaryWatch(9) == []  # impossible LED count

# Boundary case: no LEDs on
assert solution.readBinaryWatch(0) == ["0:00"]  # only midnight

# Maximum achievable LED count
assert sorted(solution.readBinaryWatch(8)) == sorted([
    "7:31", "7:47", "7:55", "7:59",
    "11:31", "11:47", "11:55", "11:59"
])  # all valid maximum-density times

# Check minute formatting
result = solution.readBinaryWatch(2)
assert "0:03" in result  # minute must be zero-padded

# Check hour formatting
assert "1:00" in solution.readBinaryWatch(1)  # no leading zero
assert "01:00" not in solution.readBinaryWatch(1)

# Verify no invalid minutes appear
for time in solution.readBinaryWatch(3):
    hour, minute = time.split(":")
    assert 0 <= int(hour) <= 11
    assert 0 <= int(minute) <= 59

# Stress test: ensure all generated times are unique
result = solution.readBinaryWatch(4)
assert len(result) == len(set(result))  # no duplicates

Test	Why
turnedOn = 1	Verifies standard functionality
turnedOn = 9	Verifies impossible configurations return empty
turnedOn = 0	Tests minimum boundary case
turnedOn = 8	Tests highest achievable LED count
Minute formatting test	Ensures leading zero handling for minutes
Hour formatting test	Ensures no leading zero for hours
Valid range verification	Confirms all outputs stay within valid time bounds
Duplicate check	Ensures each valid time appears only once

Edge Cases

Edge Case 1: turnedOn = 0

This case means no LEDs are illuminated at all. A naive implementation might accidentally return an empty list because it expects at least one active bit.

The only valid configuration is:

0:00

The implementation handles this naturally because both 0 hour bits and 0 minute bits sum to zero.

Edge Case 2: Very Large LED Counts

Inputs such as turnedOn = 9 or 10 can easily cause mistakes if the implementation assumes every LED combination corresponds to a valid time.

Although the watch physically has 10 LEDs, valid hours and minutes do not use all binary combinations. The maximum valid LED count is actually 8.

The algorithm correctly handles this by checking only valid hour and minute ranges. Since no valid pair reaches 9 or 10 set bits, the result remains empty.

Edge Case 3: Minute Formatting

Formatting minutes incorrectly is one of the most common bugs in this problem.

For example:

10:2

is invalid because minutes must always contain two digits.

The implementation explicitly formats minutes using:

f"{minute:02d}"

which guarantees proper zero-padding for all values below 10.

Edge Case 4: Hour Leading Zeros

Hours must not contain leading zeros. A careless formatting approach could generate invalid outputs such as:

01:00

The implementation avoids this by formatting the hour as a normal integer without padding.