Problem Statement & Architectural Model

A binary watch has 4 LEDs on the top representing the hours (values 8, 4, 2, 1 → valid range 0 to 11), and 6 LEDs on the bottom representing the minutes (values 32, 16, 8, 4, 2, 1 → valid range 0 to 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 lit, return all possible times the watch could represent in valid format (e.g. hour has no leading zero like "1:00", minute has two digits like "10:02").

Exhaustive Cartesian Search ($O(1)$ Constant Time)

A critical architectural insight is recognizing that the problem space is strictly finite and tiny. There are only $12 ext{ possible hours} imes 60 ext{ possible minutes} = 720 ext{ total times}$ that a 12-hour digital watch can ever display.

Rather than implementing complex recursive backtracking that manages branching trees and pruning logic, testing all 720 possible combinations takes less than 15 microseconds on modern hardware:

1. Iterate through every hour $h in [0, 11]$.
2. Iterate through every minute $m in [0, 59]$.
3. Compute the Hamming weight (number of set bits): $ ext{popcount}(h) + ext{popcount}(m)$.
4. If the sum equals turnedOn, format the string as h:mm and add to the result set.

Approach 1: High-Performance C++ using Hardware Popcount

Modern x86 and ARM processors provide dedicated single-cycle hardware instructions (such as POPCNT on x86) accessible via compiler builtins:

#include <vector>
#include <string>
#include <cstdio>

class Solution {
public:
    std::vector<std::string> readBinaryWatch(int turnedOn) {
        std::vector<std::string> result;

        // Bounded upper limit: maximum possible LEDs is 3 (hours max 11 = 1011b) + 5 (minutes max 59 = 111011b) = 8
        if (turnedOn > 8) {
            return result;
        }

        char buffer[16];

        for (int h = 0; h < 12; ++h) {
            int hBits = __builtin_popcount(h);

            for (int m = 0; m < 60; ++m) {
                if (hBits + __builtin_popcount(m) == turnedOn) {
                    std::snprintf(buffer, sizeof(buffer), "%d:%02d", h, m);
                    result.emplace_back(buffer);
                }
            }
        }

        return result;
    }
};

Approach 2: TypeScript Solution with Brian Kernighan's Algorithm

In JavaScript/TypeScript where __builtin_popcount is not directly exposed as a primitive, we can write an inline bit-counting helper using Brian Kernighan's bit-clearing trick n &= (n - 1):

/**
 * Solves LeetCode 401 using exhaustive search and Kernighan bit-counting.
 * Time Complexity: O(1) constant 720 iterations
 * Space Complexity: O(1) auxiliary
 */
export function readBinaryWatch(turnedOn: number): string[] {
  if (turnedOn > 8) return [];

  const result: string[] = [];

  function countBits(n: number): number {
    let count = 0;
    while (n > 0) {
      n &= n - 1; // Clears the lowest set bit
      count++;
    }
    return count;
  }

  for (let h = 0; h < 12; h++) {
    const hBits = countBits(h);

    for (let m = 0; m < 60; m++) {
      if (hBits + countBits(m) === turnedOn) {
        const minStr = m < 10 ? ('0' + m) : ('' + m);
        result.push(h + ':' + minStr);
      }
    }
  }

  return result;
}

Complexity Evaluation Matrix

Comparing exhaustive iteration against recursive backtracking:

Real-World Full-Stack Engineering Applications

Bit-counting and bitmask decoding appear frequently in systems programming and edge IoT web applications:

• Microcontroller Register Decoding: Interpreting 8-bit and 16-bit status registers from embedded sensors (e.g. I2C or SPI accelerometer interrupt masks) in Node.js IoT drivers.
• UNIX File Permission Bitfields: Parsing POSIX file permission modes (e.g. chmod 755 octal bitfields) in file storage gateways.
• Database Bitmapped Index Intersection: Fast cardinality evaluation across dense bitmap indexes in analytics search engines.

Frequently Asked Questions

Why can turnedOn never exceed 8 in a valid watch?

The maximum hour 11 in binary is 1011 (3 bits). The maximum minute 59 in binary is 111011 (5 bits). The maximum number of LEDs that can be simultaneously active is $3 + 5 = 8$. For any turnedOn > 8, the answer is immediately an empty array.

How does Brian Kernighan's algorithm clear bits efficiently?

Subtracting 1 from a number flips all bits up to and including the lowest set bit. Performing n & (n - 1) zeros out exactly that lowest set bit, meaning the loop executes only as many times as there are 1s in the binary representation.

Does this watch display 12-hour or 24-hour time?

The problem definition specifies hours range from 0 to 11 (4 bits: $2^0 + 2^1 + 2^2 + 2^3 = 15$, but capped at 11). It models standard 12-hour notation without AM/PM differentiation.

Is sorting required for the returned string array?

No. The problem explicitly states that results may be returned in any order. Iterating hours $0 o 11$ and minutes $0 o 59$ naturally delivers a clean, chronological sequence.

Conclusion & Performance Takeaways

LeetCode 401 proves that understanding problem domain bounds is essential to good engineering: when the total state space is bounded by a constant (720 states), a clean exhaustive Cartesian loop with hardware bit-counting outperforms complex backtracking algorithms in maintainability, predictability, and raw execution speed.