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 <= 10In #401 Binary Watch, each LED on the watch represents a binary value. The watch uses 4 LEDs for hours (0–11) and 6 LEDs for minutes (0–59). The task is to return all possible valid times where exactly turnedOn LEDs are lit.
A practical approach is to iterate through all possible hour and minute combinations. For each pair, compute the number of set bits using a bit manipulation technique such as bitCount. If the total number of set bits in the hour and minute equals turnedOn, the time is valid and can be added to the result.
Another perspective is backtracking, where you simulate turning LEDs on across the 10 positions and construct valid hour–minute pairs. However, since the total combinations are small, iterating over all valid times is simpler and efficient.
The solution benefits from the small search space (12 × 60). Bit counting helps quickly determine whether a time matches the required number of LEDs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterate Hours and Minutes with Bit Count | O(12 × 60) | O(1) (excluding output) |
| Backtracking over LED positions | O(C(10, k)) | O(k) recursion stack |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Simplify by seeking for solutions that involve comparing bit counts.
Consider calculating all possible times for comparison purposes.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Binary Watch itself is less commonly asked directly, but it represents a class of problems involving bit manipulation and combinational enumeration. Similar problems testing bit counting and small search spaces appear frequently in technical interviews.
The most practical approach is iterating through all possible hours (0–11) and minutes (0–59) and counting the number of set bits in their binary representation. If the total equals the given number of LEDs turned on, the time is valid. This works efficiently because the search space is very small.
Each LED represents a binary digit, so the number of LEDs that are on corresponds directly to the number of set bits in a number's binary representation. Bit manipulation allows you to quickly count these bits and validate possible hour and minute combinations.
No complex data structure is required for this problem. A simple list or array is enough to store valid time strings, while bit manipulation functions help count the number of set bits efficiently.