Skip to main content

401. Binary Watch

easy

Given a count of LEDs lit on a binary watch, list every valid time it could display. Pure brute-force-over-bits — small input range, but a clean popcount exercise.

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. The minute must consist of two digits and may contain a leading zero.

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

There are only 12 hour values and 60 minute values — 720 combinations total. Brute force is plenty.

Hint 2

For each (h, m) with 0 <= h < 12 and 0 <= m < 60, count the set bits in h and m. If they sum to turnedOn, emit "h:mm".

Hint 3

Use any popcount routine — built-in, Brian Kernighan, or bit-shift loop.

Solution approach

Reveal approach

Brute force with popcount. Iterate h from 0 to 11 and m from 0 to 59. For each pair, compute popcount(h) + popcount(m) using any standard set-bit counter. If the sum equals turnedOn, format the time as h + ":" + (m < 10 ? "0" : "") + m and append to the result list. The search space is tiny — 720 pairs total — so even a naïve bit-by-bit popcount is comfortably fast. O(720) ≈ O(1) time. O(1) extra space excluding the result list.

Complexity

Time
O(1) — bounded by 720
Space
O(1) extra

Related patterns

  • bit-manipulation
  • backtracking

Related problems

Asked at

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

  • Apple

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →