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 <= 10This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^10) due to recursive exploration.
Space Complexity: O(1), additional space is negligible.
| 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. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,125 views views
Watch 9 more video solutions →Practice Binary Watch with our built-in code editor and test cases.
Practice on FleetCode