Binary Watch

easy bit manipulation backtracking

Problem

A binary watch shows hours (0–11) and minutes (0–59) by LEDs in binary. Given the number of LEDs on, return all valid times "H:MM".

InputturnedOn = 1

Output["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

One LED total — either one of the six minute bits or four hour bits.

turnedOn

def read_binary_watch(turned_on):
    out = []
    for h in range(12):
        for m in range(60):
            if bin(h).count("1") + bin(m).count("1") == turned_on:
                out.append(f"{h}:{m:02d}")
    return out

function readBinaryWatch(turnedOn) {
  const out = [];
  const pop = x => { let c = 0; while (x) { c += x & 1; x >>= 1; } return c; };
  for (let h = 0; h < 12; h++) {
    for (let m = 0; m < 60; m++) {
      if (pop(h) + pop(m) === turnedOn) out.push(h + ":" + String(m).padStart(2, "0"));
    }
  }
  return out;
}

class Solution {
    public List readBinaryWatch(int turnedOn) {
        List out = new ArrayList<>();
        for (int h = 0; h < 12; h++)
            for (int m = 0; m < 60; m++)
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn)
                    out.add(String.format("%d:%02d", h, m));
        return out;
    }
}

vector readBinaryWatch(int turnedOn) {
    vector out;
    for (int h = 0; h < 12; h++)
        for (int m = 0; m < 60; m++)
            if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                char buf[8]; snprintf(buf, 8, "%d:%02d", h, m);
                out.push_back(buf);
            }
    return out;
}

Explanation

Instead of cleverly deciding which LEDs to light, this solution just checks every possible time a watch can show and keeps the ones that use the right number of LEDs. Since a clock only has 12 hours and 60 minutes, there are very few times to test.

The key idea is popcount — the number of 1 bits in a number. A watch shows hours and minutes in binary, so the LEDs that are on for a given time equal the set bits of h plus the set bits of m. So a time is valid when popcount(h) + popcount(m) equals turnedOn.

The two nested loops run h from 0 to 11 and m from 0 to 59, covering every legal time exactly once. For each pair we count the bits and, if it matches, format the time as "H:MM" with the minutes zero-padded.

Example: with turnedOn = 1, we need exactly one LED on. h = 1 with m = 0 gives one bit ("1:00"); h = 0 with m = 4 gives one bit ("0:04"). Both get collected.

Because the loop bounds are constant, the whole thing runs in constant time no matter the input, which is why it is marked O(1).

Time: O(1) Space: O(1)