401. Binary Watch
Model: qwen2.5-coder:14b
Topics: Backtracking,Bit Manipulation
FAANG asked: 1
Acceptance rate: 48.5%
Problem Breakdown
The problem involves determining all possible times that can be displayed on a binary watch given a specific number of LEDs that are turned on. The binary watch has 4 LEDs for hours (0-11) and 6 LEDs for minutes (0-59). Each LED represents a bit, with the least significant bit on the right.
Inputs:
- A non-negative integer
nrepresenting the number of LEDs that are currently on.
Outputs:
- A list of strings representing all possible times the watch could display, formatted as “H:MM”.
Implicit Constraints or Tricky Edge Cases:
- The hour must not contain a leading zero (e.g., “1:00” instead of “01:00”).
- The minute must be two digits and may contain a leading zero (e.g., “10:02” instead of “10:2”).
- If
nis 0, the only possible time is “0:00”. - If
nis greater than 9, it’s impossible to display any valid time.
Intuition
The brute-force approach would involve generating all possible combinations of hours and minutes and checking if the number of LEDs turned on matches n. However, this approach is inefficient due to its high time complexity (O(12 * 60)).
A better approach involves using bit manipulation. We can iterate through all possible hour and minute values and count the number of bits set to 1 in their binary representation. If the total number of bits matches n, we add the corresponding time to the result list.
Approach
- Iterate through all possible hours (0-11) and minutes (0-59).
- Count the number of bits set to 1 in the binary representation of each hour and minute using the built-in
bin()function andcount('1')method. - If the total number of bits matches
n, format the time string appropriately and add it to the result list.
Complexity Analysis
- Time Complexity: O(12 * 60) = O(720), which is constant since the number of hours and minutes is fixed.
- Space Complexity: O(1) for storing the result list, as the maximum size is limited by the possible combinations.
Solution
def readBinaryWatch(n: int) -> List[str]:
result = []
for hour in range(12):
for minute in range(60):
if (bin(hour).count('1') + bin(minute).count('1')) == n:
result.append(f"{hour}:{minute:02d}")
return result
Edge Cases Handled
- n = 0: The only possible time is “0:00”.
- n > 9: No valid times can be displayed, so the result list remains empty.
- Leading zeros in minutes: The format string
f"{hour}:{minute:02d}"ensures that minutes are always two digits with a leading zero if necessary.