A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.
"4:51".
Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.
The hour must not contain a leading zero.
"01:00" is not valid. It should be "1:00".The minute must consist of two digits and may contain a leading zero.
"10:2" is not valid. It should be "10:02".
Example 1:
Input: turnedOn = 1 Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
Example 2:
Input: turnedOn = 9 Output: []
Constraints:
0 <= turnedOn <= 10Problem 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.
This approach involves checking all possible times (from 00:00 to 11:59) and counting the number of LEDs that would be on, then verifying if it matches the given number of turnedOn LEDs.
The solution iterates through all possible hour (0-11) and minute (0-59) values, converts them to their binary representation, and counts the number of set bits using the built-in GCC function __builtin_popcount(). If this count matches the turnedOn LEDs, the time is formatted and added to the result set.
Time Complexity: O(12 * 60) = O(720), since it checks each minute of 12-hour cycle.
Space Complexity: O(1) for internal variables, but O(n) for the list of valid times, where n is number of valid times.
In this approach, we treat the LED numbers as a binary string simulation, where each bit can be either on or off, and explore combinations recursively. Once we reach the desired number of LEDs turned on, we check if the current hour and minute configuration is valid and add it to the results.
This C solution uses recursion to generate every possible state of the watch with up to ten LEDs. It only adds valid time representations to the result set.
Time Complexity: O(2^10) due to recursive exploration.
Space Complexity: O(1), additional space is negligible.
The problem can be converted to finding all possible combinations of i \in [0, 12) and j \in [0, 60).
A valid combination must satisfy the condition that the number of 1s in the binary representation of i plus the number of 1s in the binary representation of j equals turnedOn.
The time complexity is O(1), and the space complexity is O(1).
We can use 10 binary bits to represent the watch, where the first 4 bits represent hours and the last 6 bits represent minutes. Enumerate each number in [0, 2^{10}), check if the number of 1s in its binary representation equals turnedOn, and if so, convert it to time format and add it to the answer.
The time complexity is O(1), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(12 * 60) = O(720), since it checks each minute of 12-hour cycle. |
| Backtracking | Time Complexity: O(2^10) due to recursive exploration. |
| Enumerate Combinations | — |
| Binary Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Bit Counting | O(720) | O(1) | Best for interviews and quick implementation since the total number of times is fixed |
| Backtracking on LED Positions | O(C(10, k)) | O(k) | Useful when demonstrating recursion or generating combinations of LEDs |
Binary Watch | Simple Clean Approach | Leetcode 401 | codestorywithMIK • codestorywithMIK • 9,639 views views
Watch 9 more video solutions →Practice Binary Watch with our built-in code editor and test cases.
Practice on FleetCode