LeetCode 401: Binary Watch Solution in Python – A Step-by-Step Guide

What Is LeetCode 401: Binary Watch?

In LeetCode 401: Binary Watch, you’re given an integer turnedOn, representing how many LEDs (lights) are on. The watch has:

• 4 LEDs for hours (representing 0-11 in binary: 0000 to 1011).
• 6 LEDs for minutes (representing 0-59 in binary: 000000 to 111011).

You need to find all possible valid times (hh:mm format) where the total number of 1s across hours and minutes equals turnedOn. For example, with turnedOn = 1, times like "1:00" (hours 0001, minutes 000000) work because there’s exactly one 1.

Problem Statement

• Input: An integer turnedOn (number of LEDs on).
• Output: A list of strings—valid times in "hh:mm" format with turnedOn LEDs lit.
• Rules:
• Hours: 0-11 (4 bits).
• Minutes: 0-59 (6 bits).
• Total 1s = turnedOn.

Constraints

• 0 <= turnedOn <= 10 (max LEDs = 10).

Examples

• Input: turnedOn = 1
• Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"].
• Input: turnedOn = 9
• Output: [] (no valid time with 9 LEDs on).
• Input: turnedOn = 0
• Output: ["0:00"].

Understanding the Problem: Lighting Up Time

To solve LeetCode 401: Binary Watch in Python, we need to find all valid times where the number of 1s in the binary representation of hours (0-11) and minutes (0-59) adds up to turnedOn. A simple idea might be to try every possible hour and minute combo—but with 12 hours and 60 minutes, that’s a lot to check! Instead, we’ll use:

• Best Solution (Bit Manipulation with Iteration): O(1) time (fixed 12×60 iterations), O(1) space—uses bits to count 1s fast.
• Alternative Solution (Backtracking): O(2¹⁰) time, O(1) space—builds combinations systematically.

Let’s dive into the bit manipulation solution with a clear, step-by-step explanation.

Best Solution: Bit Manipulation with Iteration

Why This Is the Best Solution

The bit manipulation with iteration method is the top pick because it’s fast and simple—O(1) time since the problem’s scope is fixed (12 hours, 60 minutes), and O(1) space. It loops through all possible times and uses Python’s bit-counting trick to check the number of 1s, making it super efficient. It’s like flipping switches and counting lights in one smooth go!

How It Works

Think of the watch as a panel of 10 lights:

• Step 1: Loop Through Hours and Minutes:
• Hours: 0 to 11 (4 bits: 0000 to 1011).
• Minutes: 0 to 59 (6 bits: 000000 to 111011).
• Step 2: Count the 1s:
• For each hour and minute, use binary to see how many LEDs are on (1s).
• Add them up: total 1s = hour 1s + minute 1s.
• Step 3: Match the Target:
• If total 1s equals turnedOn, format it as "hh:mm" and save it.
• Step 4: Format the Time:
• Hours as-is (0-11), minutes padded with a leading zero if needed (e.g., 05).
• Step 5: Why This Works:
• There are only 12×60 = 720 possible times, so checking them all is quick.
• Bit counting (bin().count("1")) handles the binary part effortlessly.
• It’s like testing every light combo but skipping the hard work!

Step-by-Step Example

Example: turnedOn = 1

• Loop Through:
• Hour 0 (0000), Minute 0 (000000): 0 + 0 = 0 < 1, skip.
• Hour 0 (0000), Minute 1 (000001): 0 + 1 = 1, "0:01".
• Hour 0 (0000), Minute 2 (000010): 0 + 1 = 1, "0:02".
• Hour 1 (0001), Minute 0 (000000): 1 + 0 = 1, "1:00".
• Hour 2 (0010), Minute 0 (000000): 1 + 0 = 1, "2:00".
• And so on: "0:04", "0:08", "0:16", "0:32", "4:00", "8:00".
• Result: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        # Step 1: List to store valid times
        times = []

        # Step 2: Loop through all possible hours and minutes
        for hour in range(12):      # 0 to 11
            for minute in range(60):  # 0 to 59
                # Step 3: Count 1s in binary
                hour_ones = bin(hour).count("1")    # 1s in hour
                minute_ones = bin(minute).count("1")  # 1s in minute
                total_ones = hour_ones + minute_ones

                # Step 4: Check if it matches turnedOn
                if total_ones == turnedOn:
                    # Step 5: Format the time
                    time_str = f"{hour}:{minute:02d}"  # e.g., "1:05"
                    times.append(time_str)

        return times

• Line 4: Create an empty list to hold the valid times.
• Line 7-8: Loop through:
• Hours: 0 to 11 (12 possibilities).
• Minutes: 0 to 59 (60 possibilities).
• Line 10-12: Count 1s:
• bin(hour) turns hour to binary (e.g., 3 → "0b11"), .count("1") counts 1s (2).
• Same for minutes (e.g., 5 → "0b101", 3 1s).
• Add them up (e.g., 2 + 3 = 5).
• Line 15-17: If total matches turnedOn:
• Format as "hh:mm" with :02d to pad minutes (e.g., 5 → "05").
• Add to list (e.g., "3:05").
• Line 19: Return all valid times.
• Time Complexity: O(1)—fixed 12×60 = 720 iterations.
• Space Complexity: O(1)—output list is small (max 720 strings).

This is like flipping lights and checking the clock in one quick sweep!

Alternative Solution: Backtracking

Why an Alternative Approach?

The backtracking method builds times by trying all combinations of 10 LEDs (4 for hours, 6 for minutes) to get exactly turnedOn 1s. It’s O(2¹⁰) time and O(1) space—slower but shows a different way to think about it. It’s like picking which lights to turn on and seeing if they make a valid time!

How It Works

Picture it as choosing lights:

• Step 1: Start with 10 LEDs (all off: 0000 000000).
• Step 2: Pick turnedOn LEDs to turn on, try all combos.
• Step 3: Check if the first 4 bits (hours) are 0-11 and last 6 (minutes) are 0-59.
• Step 4: Format valid times.

Step-by-Step Example

Example: turnedOn = 1

• Try 1 LED on:
• 1000 000000: Hour 8, Minute 0 → "8:00".
• 0100 000000: Hour 4, Minute 0 → "4:00".
• 0010 000000: Hour 2, Minute 0 → "2:00".
• 0001 000000: Hour 1, Minute 0 → "1:00".
• 0000 000001: Hour 0, Minute 1 → "0:01".
• And so on: "0:02", "0:04", "0:08", "0:16", "0:32".
• Result: Same as above.

Code for Backtracking Approach

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

        def backtrack(pos, ones_left, hour_bits, minute_bits):
            # Base case: used all 10 positions
            if pos == 10:
                if ones_left == 0:
                    hour = int(hour_bits, 2)    # Convert binary to int
                    minute = int(minute_bits, 2)
                    if hour < 12 and minute < 60:
                        times.append(f"{hour}:{minute:02d}")
                return

            # Skip if too many ones left
            if ones_left > 10 - pos:
                return

            # Turn off this LED
            if pos < 4:
                backtrack(pos + 1, ones_left, hour_bits + "0", minute_bits)
            else:
                backtrack(pos + 1, ones_left, hour_bits, minute_bits + "0")

            # Turn on this LED
            if pos < 4:
                backtrack(pos + 1, ones_left - 1, hour_bits + "1", minute_bits)
            else:
                backtrack(pos + 1, ones_left - 1, hour_bits, minute_bits + "1")

        backtrack(0, turnedOn, "", "")
        return times

• Time Complexity: O(2¹⁰)—tries all 10-bit combinations (1024).
• Space Complexity: O(1)—excluding output.

It’s a systematic light flipper!

Comparing the Two Solutions

• Bit Manipulation (Best):
• Pros: O(1), O(1), fast and simple.
• Cons: Less flexible.
• Backtracking (Alternative):
• Pros: O(2¹⁰), O(1), explores all combos.
• Cons: Slower.

Bit manipulation wins.

Additional Examples and Edge Cases

• 0: ["0:00"].
• 10: ["11:59"] (max 1s).
• 9: [] (no valid time).

Bit manipulation handles all.

Complexity Breakdown

• Bit Manipulation: Time O(1), Space O(1).
• Backtracking: Time O(2¹⁰), Space O(1).

Bit’s the speed king.

Key Takeaways

• Bit Manipulation: Count fast!
• Backtracking: Build it up!
• Binary: Bits are fun.
• Python Tip: Strings and bits rock—see [Python Basics](/python/basics).

Final Thoughts: Light Up the Time

LeetCode 401: Binary Watch in Python is a binary time-telling adventure. Bit manipulation lights it up quick, while backtracking builds it step-by-step. Want more bit fun? Try LeetCode 191: Number of 1 Bits or LeetCode 338: Counting Bits. Ready to flip? Head to Solve LeetCode 401 on LeetCode and light up those times today!