Skip to main content

401. Binary Watch

easy

Given the number of LEDs that are on, return every valid time a binary watch could be showing. Tiny search space — the elegance is in either recursive bitmask enumeration or the bit-popcount one-liner.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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. 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. For example, '01:00' is not valid. It should be '1:00'. The minute must consist of two digits and may contain a leading zero. For example, '10:2' is not valid. It should be '10:02'.

Constraints

  • 0 <= turnedOn <= 10

Examples

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
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force: for h in 0..11, for m in 0..59, if popcount(h) + popcount(m) == turnedOn, add to result.

Hint 2

Recursive: pick which subset of 4 hour bits + 6 minute bits to turn on.

Hint 3

Backtrack over the 10 LEDs deciding on/off. When you've decided all, validate hour <= 11 and minute <= 59.

Hint 4

Both run in trivial time given the small search space.

Solution approach

Reveal approach

Two clean solutions. The one-liner: for h in 0..11, for m in 0..59, if bitCount(h) + bitCount(m) == turnedOn, push the formatted time. O(12 * 60) = O(720) — trivially fast. The recursive version: backtrack over hour LEDs and minute LEDs separately. Pick subsets of [1, 2, 4, 8] summing to a value <= 11 — these are valid hours. Pick subsets of [1, 2, 4, 8, 16, 32] summing to <= 59 — these are valid minutes. Distribute the turnedOn count across the two groups (h-leds in 0..4, m-leds = turnedOn - h-leds in 0..6) and combine. Both are O(1) in terms of the input — the search space is fixed. Default to the one-liner for clarity.

Complexity

Time
O(1) — fixed 12 * 60
Space
O(1)

Related patterns

  • recursion
  • backtracking
  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Apple
  • Amazon

Practice these live with InterviewChamp.AI

Drill Binary Watch and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →