Binary Watch - Video Solutions

Problem Overview: A binary watch represents hours and minutes using LEDs. The top 4 LEDs represent hours (0–11) and the bottom 6 represent minutes (0–59). Given an integer turnedOn, return all valid times where exactly that many LEDs are on.

Approach 1: Brute Force Enumeration with Bit Counting (Time: O(720), Space: O(1) excluding output)

The watch has only 12 * 60 = 720 possible times, so you can iterate through every valid hour and minute combination. For each pair, count how many bits are set in hour and minute. If the total equals turnedOn, format the time and add it to the result. Bit counting can be done using built-in functions such as __builtin_popcount in C++ or bin(x).count('1') in Python. This approach works because the search space is tiny and bounded, making the complexity effectively constant.

Bit manipulation is the key idea here: each LED corresponds to a bit. Counting the number of set bits tells you how many LEDs are active. The approach is straightforward to implement and easy to reason about during interviews.

Approach 2: Backtracking Over LED Positions (Time: O(C(10, k)), Space: O(k) recursion)

A binary watch has exactly 10 LEDs (4 for hours and 6 for minutes). Instead of checking every time, treat the LEDs as positions and use backtracking to choose exactly turnedOn LEDs. As you build a combination, maintain the numeric value of hours and minutes based on which LEDs are selected.

During recursion, if the hour exceeds 11 or the minute exceeds 59, prune that branch immediately. Once exactly turnedOn LEDs are selected, format the resulting hour and minute into a valid time string. The recursion explores combinations of LED indices while updating values using bit manipulation logic.

This approach avoids scanning all 720 times and instead focuses on LED combinations. The theoretical complexity is O(C(10, k)), where k is the number of LEDs turned on. Since the number of LEDs is small, the recursion tree remains manageable.

Recommended for interviews: The brute force enumeration is usually the fastest path during interviews. It shows clear reasoning: iterate through all valid times and count set bits. Interviewers often accept this immediately because the input space is fixed and small. The backtracking solution demonstrates stronger algorithmic thinking and familiarity with recursion patterns, which can help if the interviewer pushes for a more combinational approach.