Binary Watch

Difficulty: Easy | Acceptance: 65.50% | Paid: No Topics: Backtracking, Bit Manipulation

A binary watch has 4 LEDs on the top which represent the hours (0-11), and 6 LEDs on the bottom which represent the minutes (0-59). Each LED represents a binary digit (0 or 1), with the least significant bit on the right.

Given an integer turnedOn which represents the number of LEDs that are currently on, return all possible times the watch could represent. You may return the answer in any order.

The hour must not contain a leading zero, for example “01:00” is not valid. It should be “1:00”. The minute must consist of two digits and may contain a leading zero, for example “10:2” is not valid. It should be “10:02”.

• Examples
• Constraints
• Brute Force
• Backtracking
• Bit Manipulation with Precomputation

Examples

Example 1:

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

Example 2:

Input: turnedOn = 9
Output: []

Constraints

0 <= turnedOn <= 10

Brute Force

Intuition Iterate through all valid hour (0-11) and minute (0-59) combinations, count the set bits in each, and collect times where the total matches turnedOn.

Steps

• Loop through all hours from 0 to 11
• Loop through all minutes from 0 to 59
• Count the number of 1 bits in hour and minute
• If the sum equals turnedOn, format and add the time to result

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        result = []
        for h in range(12):
            for m in range(60):
                if bin(h).count('1') + bin(m).count('1') == turnedOn:
                    result.append(str(h) + ':' + str(m).zfill(2))
        return result

Complexity

• Time: O(1) - Fixed 12 × 60 = 720 iterations
• Space: O(1) - Output space excluded, constant extra space
• Notes: Simple and efficient enough for this problem

Backtracking

Intuition Use backtracking to explore all combinations of turning on exactly turnedOn LEDs across the 10 positions (4 for hours, 6 for minutes), filtering invalid times.

Steps

• Use recursive backtracking to select which LEDs to turn on
• Track current hour and minute values
• When exactly turnedOn LEDs are selected, check if time is valid
• Add valid times to result

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        result = []
        
        def backtrack(count, start, hours, minutes):
            if count == turnedOn:
                if hours < 12 and minutes < 60:
                    result.append(str(hours) + ':' + str(minutes).zfill(2))
                return
            for i in range(start, 10):
                if i < 4:
                    backtrack(count + 1, i + 1, hours + (1 << i), minutes)
                else:
                    backtrack(count + 1, i + 1, hours, minutes + (1 << (i - 4)))
        
        backtrack(0, 0, 0, 0)
        return result

Complexity

• Time: O(C(10, turnedOn)) - At most C(10,5) = 252 combinations
• Space: O(turnedOn) - Recursion stack depth
• Notes: More elegant but similar efficiency to brute force

Bit Manipulation with Precomputation

Intuition Precompute the number of set bits for all possible hours (0-11) and minutes (0-59), then use lookup tables to find valid combinations.

Steps

• Create arrays mapping each hour/minute to its bit count
• Iterate through all hour-minute pairs
• Use precomputed bit counts to check validity
• Format and collect valid times

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        # Precompute bit counts
        hour_bits = [bin(i).count('1') for i in range(12)]
        minute_bits = [bin(i).count('1') for i in range(60)]
        
        result = []
        for h in range(12):
            for m in range(60):
                if hour_bits[h] + minute_bits[m] == turnedOn:
                    result.append(str(h) + ':' + str(m).zfill(2))
        return result

Complexity

• Time: O(1) - Fixed 12 × 60 = 720 iterations with O(1) lookup
• Space: O(1) - Fixed size precomputed arrays (12 + 60 = 72 elements)
• Notes: Slightly faster bit counting at the cost of minimal extra space