Binary Watch — Easy Problem & Solution

A binary watch shows the hour with 4 LEDs (values 1, 2, 4, 8) and the minute with 6 LEDs (values 1, 2, 4, 8, 16, 32).

Difficulty: Easy
Topics: Bit Manipulation, Backtracking, Enumeration
Asked at: Amazon, Adobe, Oracle
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A binary watch shows the hour with 4 LEDs (values 1, 2, 4, 8) and the minute with 6 LEDs (values 1, 2, 4, 8, 16, 32). Hours run from 0 to 11 and minutes from 0 to 59.

Given the number of LEDs that are lit, return every time the watch could be showing, formatted as "H:MM" — the hour without a leading zero and the minute always two digits.

List the times in increasing order of hour, then of minute.

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"]
Explanation: Exactly one LED is lit, so either one minute bit or one hour bit.

Example 2

Input: turnedOn = 9
Output: []
Explanation: No valid time lights nine LEDs.

Example 3

Input: turnedOn = 0
Output: ["0:00"]

Constraints

0 <= turnedOn <= 10

How to solve Binary Watch

The search space is tiny, so enumerate every legal time and keep the ones whose total popcount matches.

Approach

Loop h from 0 to 11 and m from 0 to 59.
If popcount(h) + popcount(m) == turnedOn, format the time and collect it.
The nested loop order already yields hour-then-minute ordering.

Why it works

Every reachable display corresponds to exactly one (h, m) pair, and the lit LEDs are exactly the set bits of the two numbers — so the popcount sum is the number of lit LEDs.

Complexity

Time — O(720)
Space — O(output)

Pitfalls

Forgetting to zero-pad the minute produces "1:0" instead of "1:00".
Padding the hour as well produces "01:00", which the format does not use.
Enumerating LED subsets instead of times is more work and risks duplicates.

Reference solution

Python

from typing import List

def readBinaryWatch(turnedOn: int) -> List[str]:
    out = []
    for h in range(12):
        for m in range(60):
            if bin(h).count("1") + bin(m).count("1") == turnedOn:
                out.append("{}:{:02d}".format(h, m))
    return out

JavaScript

var readBinaryWatch = function(turnedOn) {
    var bits = function(x) {
        var c = 0;
        while (x > 0) { c += x & 1; x >>= 1; }
        return c;
    };
    var out = [];
    for (var h = 0; h < 12; h++) {
        for (var m = 0; m < 60; m++) {
            if (bits(h) + bits(m) === turnedOn) {
                out.push(String(h) + ":" + (m < 10 ? "0" + String(m) : String(m)));
            }
        }
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 83 bit manipulation problems · the whole catalogue