Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every valid time has a unique combination of hour and minute bits, and its number of lit LEDs is the sum of their set-bit counts. There are only 720 valid times, so enumerating times avoids generating invalid LED combinations such as hour 15 or minute 63.

Approach

Enumerate hours from zero through 11 and minutes from zero through 59.
Count each value's set bits by repeatedly inspecting its lowest binary digit and dividing by two.
Keep the pair when the two counts sum to turnedOn.
Format the hour without padding and the minute with exactly two digits. Return all matching strings; if no valid time has the requested number of lit LEDs, the result is empty.

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

        def bit_count(n):
            count = 0

            while n:
                if n % 2 == 1:
                    count += 1
                n //= 2

            return count

        for h in range(12):
            for m in range(60):
                if bit_count(h) + bit_count(m) == turnedOn:
                    m = str(m)
                    m = m if len(m) > 1 else '0' + m
                    res.append(str(h) + ':' + m)

        return res

Complexity analysis

The displayed ranges contain only 12 × 60 = 720 candidate times, so time and auxiliary working space are O(1) under the fixed watch domain; the returned strings occupy O(A) space for A matching times.