Binary Watch
Easy · Bit Manipulation · Backtracking · Bit Manipulation
Problem
A binary watch shows the hour with 4 LEDs (worth 8, 4, 2 and 1, for hours 0 to 11) and the minute with 6 LEDs (worth 32, 16, 8, 4, 2 and 1, for minutes 0 to 59). The hour or minute shown is the sum of its lit LEDs.
Given turnedOn, the number of LEDs that are lit, return every valid time the watch could be showing, in any order.
Write each time as "h:mm": the hour has no leading zero ("1:00", never "01:00"), and the minute always has two digits ("10:02", never "10:2"). A combination of LEDs that adds up to an hour above 11 or a minute above 59 is not a valid time.
Examples
Input: turnedOn = 1 Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
With one LED lit, the time is either one minute LED with hour 0, or one hour LED with minute 00.
Input: turnedOn = 9 Output: []
At most 3 hour LEDs (11) and 5 minute LEDs (59) can be lit together, so 9 is impossible.
Input: turnedOn = 0 Output: ["0:00"]
With nothing lit, the watch shows 0:00.
Constraints
- 0 <= turnedOn <= 10
Approaches
- Choose which LEDs are lit — time O(C(10, turnedOn)), space O(turnedOn) for the recursion
Follow-up
Turning the question around, from "which LEDs" to "which numbers have this many 1 bits", leads to counting such numbers in a huge range without listing them (the first use case) and to stepping from a number to the next one with the same count of 1 bits (the second).
Related problems
Start free on Cariara · Coding problems · System design studio
