Facebook Pixel

401. Binary Watch

EasyBit ManipulationBacktracking
Leetcode Link

Problem Description

A binary watch displays time using LEDs - 4 LEDs on top represent hours (0-11) and 6 LEDs on bottom represent minutes (0-59). Each LED can be either on (1) or off (0), representing the time in binary format.

Given an integer turnedOn representing the total number of LEDs that are currently lit, you need to find all possible valid times the watch could be displaying.

Key requirements:

  • Hours range from 0 to 11 (represented by 4 bits)
  • Minutes range from 0 to 59 (represented by 6 bits)
  • Hours should not have leading zeros (e.g., "1:00" not "01:00")
  • Minutes must always be two digits with leading zero if needed (e.g., "10:02" not "10:2")
  • Return all possible times where exactly turnedOn LEDs are lit

Solution Explanation:

The solution uses a brute force approach by iterating through all possible valid times (12 hours × 60 minutes = 720 combinations). For each hour-minute combination:

  1. It counts the number of 1s in the binary representation of both the hour and minute values
  2. If the total count of 1s equals turnedOn, this time is included in the result
  3. The time is formatted as "H:MM" using '{:d}:{:02d}'.format(i, j)

The key insight is that bin(i) + bin(j) concatenates the binary strings, and .count('1') counts all the '1' characters (lit LEDs) in both the hour and minute representations. This directly corresponds to counting how many LEDs are turned on for that particular time.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • No: The problem doesn't involve nodes and edges or graph traversal. We're dealing with a binary watch representation.

Need to solve for kth smallest/largest?

  • No: We're not looking for the kth smallest or largest element. We need to find all possible valid times.

Involves Linked Lists?

  • No: The problem doesn't involve linked lists or pointer manipulation.

Does the problem have small constraints?

  • Yes: The constraints are very small - we only have 10 total LEDs (4 for hours + 6 for minutes), and valid hours are 0-11 and minutes are 0-59. The maximum value of turnedOn is 10.

Brute force / Backtracking?

  • Yes: Given the small constraints, we can either:
    • Use brute force to check all 720 possible times (12 hours × 60 minutes)
    • Use backtracking to generate all combinations of turning on exactly turnedOn LEDs from the 10 available LEDs

Conclusion: The flowchart correctly leads us to use a brute force/backtracking approach. The solution implements the brute force variant - iterating through all possible valid times and checking if the number of set bits (lit LEDs) in their binary representations equals turnedOn. This is efficient given the small problem space and avoids the complexity of implementing a full backtracking solution to generate combinations.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is recognizing that each valid time on the binary watch corresponds to a specific number of lit LEDs. Since hours are represented by 4 bits and minutes by 6 bits, any time can be represented by counting the '1's in the binary representation of both values.

For example, if the time is 3:05:

  • Hour 3 in binary is 0011 (2 LEDs lit)
  • Minute 5 in binary is 000101 (2 LEDs lit)
  • Total LEDs lit = 4

Instead of trying to generate all possible combinations of turning on exactly turnedOn LEDs and then checking if they form valid times, we can flip the problem around. We iterate through all valid times (which is a small, fixed set of 720 possibilities) and check which ones have exactly turnedOn LEDs lit.

This reverse approach is simpler because:

  1. We automatically ensure valid times (hours 0-11, minutes 0-59)
  2. We avoid complex bit manipulation to generate LED combinations
  3. Counting set bits in a number is straightforward using bin(n).count('1')

The brute force nature of checking all 720 possible times is acceptable here because the problem space is inherently small and bounded. This makes it more efficient than implementing a complex backtracking algorithm to generate valid LED combinations and then converting them to times.

Solution Approach

The solution uses a list comprehension with nested loops to generate all valid times that match the turnedOn constraint.

Implementation walkthrough:

  1. Iterate through all valid hours and minutes:

    • Outer loop: for i in range(12) - iterates through hours 0 to 11
    • Inner loop: for j in range(60) - iterates through minutes 0 to 59
    • This gives us all 720 possible valid times
  2. Count the number of lit LEDs for each time:

    • bin(i) converts the hour to binary string (e.g., bin(3) returns '0b11')
    • bin(j) converts the minute to binary string (e.g., bin(5) returns '0b101')
    • (bin(i) + bin(j)) concatenates both binary strings
    • .count('1') counts all '1' characters in the concatenated string, which represents the total number of lit LEDs
  3. Filter times based on the LED count:

    • The condition if (bin(i) + bin(j)).count('1') == turnedOn ensures we only include times where exactly turnedOn LEDs are lit
  4. Format the output:

    • '{:d}:{:02d}'.format(i, j) formats the time string properly
    • {:d} formats the hour as a decimal integer (no leading zeros)
    • {:02d} formats the minute as a two-digit decimal with leading zero if needed

Data structures used:

  • List comprehension to build the result list efficiently
  • No additional data structures needed due to the straightforward iteration approach

Time Complexity: O(1) - Since we always check exactly 720 combinations (12 × 60), the time complexity is constant regardless of input

Space Complexity: O(1) - The output size depends on turnedOn but is bounded by the maximum of 720 possible times

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with turnedOn = 2.

We'll iterate through all possible times and check which ones have exactly 2 LEDs lit:

Step 1: Check time 0:01

  • Hour 0 in binary: 0000 → 0 LEDs lit
  • Minute 1 in binary: 000001 → 1 LED lit
  • Total: 0 + 1 = 1 LED (not equal to 2, skip)

Step 2: Check time 0:03

  • Hour 0 in binary: 0000 → 0 LEDs lit
  • Minute 3 in binary: 000011 → 2 LEDs lit
  • Total: 0 + 2 = 2 LEDs ✓
  • Add "0:03" to result

Step 3: Check time 1:01

  • Hour 1 in binary: 0001 → 1 LED lit
  • Minute 1 in binary: 000001 → 1 LED lit
  • Total: 1 + 1 = 2 LEDs ✓
  • Add "1:01" to result

Step 4: Check time 3:00

  • Hour 3 in binary: 0011 → 2 LEDs lit
  • Minute 0 in binary: 000000 → 0 LEDs lit
  • Total: 2 + 0 = 2 LEDs ✓
  • Add "3:00" to result

Step 5: Check time 3:01

  • Hour 3 in binary: 0011 → 2 LEDs lit
  • Minute 1 in binary: 000001 → 1 LED lit
  • Total: 2 + 1 = 3 LEDs (not equal to 2, skip)

The algorithm continues through all 720 combinations. When turnedOn = 2, the final result would be:

["0:03", "0:05", "0:06", "0:09", "0:10", "0:12", "0:17", "0:18", "0:20", "0:24", "0:33", "0:34", "0:36", "0:40", "0:48", "1:01", "1:02", "1:04", "1:08", "1:16", "1:32", "2:01", "2:02", "2:04", "2:08", "2:16", "2:32", "3:00", "4:01", "4:02", "4:04", "4:08", "4:16", "4:32", "5:00", "6:00", "8:01", "8:02", "8:04", "8:08", "8:16", "8:32", "9:00", "10:00"]

The key insight is that by checking all valid times, we automatically handle the formatting requirements and valid ranges while simply counting the bits to match our constraint.

Solution Implementation

1class Solution:
2    def readBinaryWatch(self, turnedOn: int) -> List[str]:
3        """
4        Find all possible times a binary watch could display given the number of LEDs turned on.
5      
6        A binary watch has 4 LEDs for hours (0-11) and 6 LEDs for minutes (0-59).
7        We need to find all valid times where the total number of lit LEDs equals turnedOn.
8      
9        Args:
10            turnedOn: The number of LEDs currently turned on (0-10)
11          
12        Returns:
13            List of valid times in "H:MM" format
14        """
15        # List to store all valid time combinations
16        result = []
17      
18        # Iterate through all possible hours (0-11)
19        for hour in range(12):
20            # Iterate through all possible minutes (0-59)
21            for minute in range(60):
22                # Count the number of 1s in binary representation of both hour and minute
23                # bin() returns string like '0b101', so we count '1' characters
24                hour_bits = bin(hour).count('1')
25                minute_bits = bin(minute).count('1')
26              
27                # Check if total lit LEDs matches the required number
28                if hour_bits + minute_bits == turnedOn:
29                    # Format time as "H:MM" (hour without leading zero, minute with leading zero)
30                    time_string = f"{hour}:{minute:02d}"
31                    result.append(time_string)
32      
33        return result
34
1class Solution {
2    /**
3     * Finds all possible times that can be displayed on a binary watch
4     * when exactly 'turnedOn' LEDs are lit.
5     * 
6     * @param turnedOn The number of LEDs currently on
7     * @return List of valid times in "H:MM" format
8     */
9    public List<String> readBinaryWatch(int turnedOn) {
10        // List to store all valid time combinations
11        List<String> result = new ArrayList<>();
12      
13        // Iterate through all possible hours (0-11)
14        for (int hour = 0; hour < 12; hour++) {
15            // Iterate through all possible minutes (0-59)
16            for (int minute = 0; minute < 60; minute++) {
17                // Count the number of set bits (1s) in binary representation
18                // of both hour and minute values
19                int totalBitsSet = Integer.bitCount(hour) + Integer.bitCount(minute);
20              
21                // If the total number of set bits equals the turned on LEDs,
22                // this is a valid time combination
23                if (totalBitsSet == turnedOn) {
24                    // Format the time string with leading zero for minutes if needed
25                    String timeString = String.format("%d:%02d", hour, minute);
26                    result.add(timeString);
27                }
28            }
29        }
30      
31        return result;
32    }
33}
34
1class Solution {
2public:
3    vector<string> readBinaryWatch(int turnedOn) {
4        vector<string> result;
5      
6        // Iterate through all possible hour values (0-11)
7        for (int hour = 0; hour < 12; ++hour) {
8            // Iterate through all possible minute values (0-59)
9            for (int minute = 0; minute < 60; ++minute) {
10                // Count the number of set bits (1s) in binary representation
11                // of both hour and minute values
12                int hourBits = __builtin_popcount(hour);
13                int minuteBits = __builtin_popcount(minute);
14              
15                // Check if total number of LEDs turned on matches the requirement
16                if (hourBits + minuteBits == turnedOn) {
17                    // Format the time string
18                    // Add leading zero for minutes less than 10
19                    string timeString = to_string(hour) + ":" + 
20                                       (minute < 10 ? "0" : "") + 
21                                       to_string(minute);
22                  
23                    result.push_back(timeString);
24                }
25            }
26        }
27      
28        return result;
29    }
30};
31
1/**
2 * Generates all possible times for a binary watch with a given number of LEDs turned on
3 * @param turnedOn - Number of LEDs that are turned on
4 * @returns Array of time strings in "h:mm" format
5 */
6function readBinaryWatch(turnedOn: number): string[] {
7    // Base case: no LEDs turned on means "0:00"
8    if (turnedOn === 0) {
9        return ['0:00'];
10    }
11  
12    // Total number of bits (4 for hours + 6 for minutes)
13    const TOTAL_BITS = 10;
14    const result: string[] = [];
15  
16    // Bit array representing LED states (first 4 bits for hours, last 6 for minutes)
17    const ledStates: boolean[] = new Array(TOTAL_BITS).fill(false);
18  
19    /**
20     * Converts the current LED state array into hours and minutes
21     * @returns Tuple of [hours, minutes]
22     */
23    const convertToTime = (): [number, number] => {
24        // Extract hours from first 4 bits
25        const hours = ledStates
26            .slice(0, 4)
27            .reduce((accumulated, bit) => (accumulated << 1) | Number(bit), 0);
28      
29        // Extract minutes from last 6 bits
30        const minutes = ledStates
31            .slice(4)
32            .reduce((accumulated, bit) => (accumulated << 1) | Number(bit), 0);
33      
34        return [hours, minutes];
35    };
36  
37    /**
38     * Recursive helper function to generate all combinations of turned on LEDs
39     * @param currentIndex - Current position in the LED array
40     * @param remainingLeds - Number of LEDs still to be turned on
41     */
42    const generateCombinations = (currentIndex: number, remainingLeds: number): void => {
43        // Pruning: impossible to place remaining LEDs in available positions
44        if (currentIndex + remainingLeds > TOTAL_BITS || remainingLeds === 0) {
45            return;
46        }
47      
48        // Choose: turn on LED at current position
49        ledStates[currentIndex] = true;
50      
51        // If this is the last LED to place, check if time is valid
52        if (remainingLeds === 1) {
53            const [hours, minutes] = convertToTime();
54          
55            // Valid time check: hours < 12 and minutes < 60
56            if (hours < 12 && minutes < 60) {
57                // Format time string with zero-padding for minutes
58                const timeString = `${hours}:${minutes < 10 ? '0' + minutes : minutes}`;
59                result.push(timeString);
60            }
61        }
62      
63        // Explore: recurse with current LED on
64        generateCombinations(currentIndex + 1, remainingLeds - 1);
65      
66        // Unchoose: turn off LED at current position
67        ledStates[currentIndex] = false;
68      
69        // Explore: recurse without turning on current LED
70        generateCombinations(currentIndex + 1, remainingLeds);
71    };
72  
73    // Start the recursive generation
74    generateCombinations(0, turnedOn);
75  
76    return result;
77}
78

Time and Space Complexity

Time Complexity: O(1)

The algorithm iterates through all possible hour values (0-11) and minute values (0-59), which gives us a fixed number of iterations: 12 × 60 = 720. For each combination, it performs:

  • Binary conversion using bin() function: O(log i) + O(log j), but since i ≤ 11 and j ≤ 59, these are bounded by constants
  • String concatenation: O(1) for small fixed-size strings
  • Counting '1's in the binary representation: O(log i) + O(log j), again bounded by constants
  • String formatting: O(1)

Since we perform a constant number of operations (720 iterations with constant-time work per iteration), the overall time complexity is O(1).

Space Complexity: O(1)

The space complexity consists of:

  • The output list containing valid time combinations. In the worst case (when turnedOn equals the optimal number of LEDs), the maximum number of valid combinations is still bounded by 720 (all possible hour-minute combinations)
  • Temporary variables for iteration and string operations: O(1)

Since the maximum size of the output is bounded by a constant (at most 720 valid times), the space complexity is O(1).

Common Pitfalls

1. Incorrect Time Formatting

One of the most common mistakes is formatting the output incorrectly, particularly with the minute representation.

Pitfall Example:

# Wrong - doesn't pad minutes with leading zero
time_string = f"{hour}:{minute}"  # Results in "10:2" instead of "10:02"

# Wrong - pads hours unnecessarily  
time_string = f"{hour:02d}:{minute:02d}"  # Results in "01:00" instead of "1:00"

Correct Solution:

# Correct - hour without padding, minute with 2-digit padding
time_string = f"{hour}:{minute:02d}"

2. Inefficient Bit Counting

Some developers might try to manually convert and count bits, leading to more complex and error-prone code.

Pitfall Example:

# Overly complex manual bit counting
def count_bits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Then using it for both hour and minute
if count_bits(hour) + count_bits(minute) == turnedOn:
    # ...

Better Solution:

# Use Python's built-in bin() and count()
if bin(hour).count('1') + bin(minute).count('1') == turnedOn:
    # ...

3. Wrong Range Boundaries

Using incorrect ranges for hours or minutes is another frequent error.

Pitfall Example:

# Wrong - hours can go up to 12 (invalid)
for hour in range(13):  # Should be range(12)
  
# Wrong - missing the last minute
for minute in range(59):  # Should be range(60)

Correct Solution:

for hour in range(12):    # 0-11 inclusive
    for minute in range(60):  # 0-59 inclusive

4. Alternative Approach Pitfall: Combination Generation

Some might try to use combinations to generate all possible LED patterns, which is more complex and harder to validate.

Pitfall Example:

from itertools import combinations

# Trying to generate all combinations of turnedOn LEDs from 10 total LEDs
# This approach requires mapping bit positions to valid times
all_leds = list(range(10))  # 4 for hours + 6 for minutes
for combo in combinations(all_leds, turnedOn):
    # Complex logic to map LED positions to time values
    # Easy to make mistakes in bit position mapping

Why the Brute Force is Better: The straightforward iteration through all 720 possible times is cleaner, less error-prone, and actually efficient since the problem space is small and bounded.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More