Binary Watch (LeetCode 401)
You will see how treating every LED pattern as one 10-bit number turns Binary Watch into a single loop over 1024 masks.
A binary watch shows the time with 10 LEDs. Four LEDs on the top encode the hour (0 to 11) and six LEDs on the bottom encode the minute (0 to 59); each LED is one bit, with the lowest bit on the right.
Given turnedOn, the number of LEDs that are lit, return every time the watch could be showing, in any order. Write the hour without a leading zero ("1:00", never "01:00") and the minute with exactly two digits ("10:02", never "10:2").
Worked Examples
turnedOn = 1["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]turnedOn = 9[]⚖️Formal Constraints & Bounds
0 <= turnedOn <= 10
Why It Works & Core Invariant
There are only 2^10 patterns of lit LEDs, and each is a number: test every mask, keep the ones with turnedOn bits, and decode the hour and minute fields with a shift and a mask, checking each field's range.
Real-World Scenario & Production Applications
Feature flags, permission sets and hardware status registers are all packed into integers, one bit per option. Enumerating every combination of a few flags (for example, to test each configuration) is a loop over range(1 << n), and decoding a register means shifting and masking its fields, then validating each one.
Subproblems & Recurrence Decomposition3 Phases
Leverage bitwise properties: x ^ x = 0 (cancellation), n & (n - 1) (clears lowest set bit), or right-shift induction dp[i] = dp[i >> 1] + (i & 1).
# Brian Kernighan Bit-Clearing:
# n & (n - 1) clears lowest set bit in O(1)Step-by-Step Execution Trace Table
Input turnedOn = 2: only masks with exactly two 1 bits pass the popcount check (45 of the 1024).
mask (binary, hour bits | minute bits) | hour = mask >> 6 | minute = mask & 0b111111 | hour < 12 and minute < 60? | Action |
|---|---|---|---|---|
0000 | 000011 = 3 | 0 | 3 | Yes | append "0:03" |
0000 | 000101 = 5 | 0 | 5 | Yes | append "0:05" |
| ... | ||||
0000 | 110000 = 48 | 0 | 48 | Yes | append "0:48" |
0001 | 000001 = 65 | 1 | 1 | Yes | append "1:01" |
| ... | ||||
1100 | 000000 = 768 | 12 | 0 | No (hour 12) | skip: 4 bits can spell 12 |
| End | 44 times returned |
| 1 | Every pattern of the 10 LEDs is one number from 0 to 1023: bit `i` is on when LED `i` is lit. |
| 2 | Keep a mask only when `bin(mask).count("1") == turnedOn`; its top 4 bits are the hour (`mask >> 6`) and its low 6 bits the minute (`mask & 0b111111`). |
| 3 | Loop `for mask in range(1 << 10)`, skip wrong popcounts, split into `hour, minute`, check the ranges, append `f"{hour}:{minute:02d}"`, return the list. |
| 4 | The trap: check `hour < 12 and minute < 60` after splitting, because 4 bits reach 15 and 6 bits reach 63. |
Target: Binary Watch (LeetCode 401). The 10 LEDs are the items, so the 1024 masks are every possible pattern of lit LEDs, each visited once.
Bit positions are independent channels processed simultaneously in 1 CPU cycle. n & (n - 1) clears lowest set bit; x ^ x = 0 cancels pairs.
while n > 0: n &= n - 1 (terminates after K cycles, K = set bits); or O(1) bitwise expressions.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
When a problem has only a handful of on/off items, every subset is just a number. Give item i bit i: a number whose bit i is 1 means "item i is chosen". The subsets of n items are then exactly the numbers 0 .. 2^n - 1, so one for mask in range(1 << n) loop visits each subset once, with no recursion and no duplicates. Binary Watch is the purest case: the 10 LEDs are the items, and a lit LED is a 1 bit.
🏟️ The Analogy: A Row of Light Switches
Ten switches on a wall are a 10-digit binary number. Counting from 0 to 1023 flips them through every possible pattern exactly once. Reading the pattern back is just as easy: the left 4 switches spell the hour in binary, the right 6 spell the minute.
🪄 The Mathematical Harmony / Magic Trick
for mask in range(1 << 10): # every pattern of 10 LEDs if bin(mask).count("1") != turnedOn: # popcount = lit LEDs continue hour, minute = mask >> 6, mask & 0b111111 if hour < 12 and minute < 60: # 4 bits reach 15, 6 bits reach 63 times.append(f"{hour}:{minute:02d}") mask >> 6 drops the 6 minute bits and leaves the hour; mask & 0b111111 keeps only the minute bits. The range check matters: a field of 4 bits can hold 12 to 15, which are not hours, and 6 bits can hold 60 to 63, which are not minutes.
💡 Summary
Small n plus "try every combination" means: loop over range(1 << n), read the subset from the bits, and validate each decoded field. masks with a 10-bit popcount each is a fixed amount of work.
Skipping the range check:
hour < 12 and minute < 60must follow the split. ForturnedOn = 2the mask1100 000000decodes to hour 12, and forturnedOn = 4the minute bits111100decode to 60; both are impossible times.Wrong field split: the hour is the top 4 bits,
mask >> 6; the minute is the low 6 bits,mask & 0b111111(63). Usingmask & 0b1111ormask >> 4mixes hour and minute LEDs.Formatting: the minute needs two digits (
f"{minute:02d}") and the hour none extra ("1:00", not"01:00").Forgetting
turnedOn = 0: the empty pattern, mask 0, is the valid time"0:00";range(1 << 10)starts at 0, so it is included.
4-Phase Thought Process Model
You will see how a senior engineer spots a bitmask enumeration and names its one real trap.
Pattern Recognition Signals
The 10-second spot
"10 LEDs", each on or off, and "return all possible times": a small, fixed set of on/off items where you must try every combination. With n = 10 there are only 1024 subsets, so each subset can simply be a number: Bitmask Subsets.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Bit i of mask is on exactly when LED i is lit, so range(1 << 10) visits each pattern once; a pattern is kept when bin(mask).count("1") == turnedOn and its decoded hour, minute = mask >> 6, mask & 0b111111 pass hour < 12 and minute < 60.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
if hour < 12 and minute < 60:: check each field after the split, because 4 bits reach 15 and 6 bits reach 63 (turnedOn = 2already produces hour 12).hour, minute = mask >> 6, mask & 0b111111: the hour is the top 4 bits, the minute the low 6; any other split mixes the two rows of LEDs.f"{hour}:{minute:02d}": two-digit minute, no leading zero on the hour.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd treat this as Bitmask Subsets. The watch has ten LEDs, so every pattern of lit LEDs is one number from 0 to 1023, with bit i on when LED i is lit. I loop over all 1024 masks and keep the ones whose popcount equals turnedOn. Then I decode: the top four bits, mask shifted right by six, are the hour, and the low six bits, mask and 63, are the minute. The trap is validation: four bits can spell up to 15 and six bits up to 63, so I keep a time only when the hour is below 12 and the minute below 60, and I format the minute with two digits. Each subset is one number, so every pattern is checked exactly once. It's 1024 masks with a 10-bit popcount each, a constant amount of work, and constant extra space beyond the answer.
So: 10 LEDs means 1024 masks; filter by popcount, split with >> 6 and & 0b111111, and range-check both fields.
Complexity & Mathematical Proof
O(B * 2^B), B = 10 LEDs
Look at the code: for mask in range(1 << 10) runs 2^B = 1024 times. Each iteration builds bin(mask) and counts its 1s in O(B), then does a shift, a mask and two comparisons in O(1). Total: O(B * 2^B) = about 10,000 basic steps, whatever turnedOn is.
O(1) extra, output not counted
Apart from the answer, the loop keeps mask, hour and minute and a short bin string of at most B + 2 characters: O(1) extra. The answer holds at most 720 times (12 hours x 60 minutes) and is not counted.
T = 2^B · O(B) = O(B · 2^B), B = 10
Look at the code: for mask in range(1 << 10) runs 2^B = 1024 times. Each iteration builds bin(mask) and counts its 1s in O(B), then does a shift, a mask and two comparisons in O(1). Total: O(B * 2^B) = about 10,000 basic steps, whatever turnedOn is.
Derivation Progression
2^B = 1024 iterations
for mask in range(1 << 10) visits every LED pattern once.
O(B) per mask
bin(mask).count("1") looks at each of the B bits.
O(1) per kept mask
One shift, one AND, two comparisons and a short format.
O(B · 2^B)
About 10,000 steps: a constant, independent of turnedOn.
Variable Definitions
Number of LEDs (bits), 10 on this watch
One pattern of lit LEDs, a number from 0 to 2^B - 1
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): mask, hour, minute, one bin string
At most 720 time strings (not counted)
Boundary Best / Worst Cases
: all masks are visited even when turnedOn is 0 or 10
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "4 LEDs for the hour, 6 for the minute", "every time the watch could show". A fixed, tiny set of on/off items (10 bits) and an "every combination" question: Bitmask Subsets, one number per subset.
turnedOn and exactly bits, so masks: constant work. Bitmask enumeration stays practical up to about items ( masks).
Decoded fields must be range-checked (hour 12-15 and minute 60-63 are representable but invalid). In production bit fields, the same rule holds for any packed register or flag word: validate every field after masking, since reserved or out-of-range values can be encoded.
Core Algorithmic State Invariants
Bit `i` of `mask` is on exactly when LED `i` is lit, so every number in `range(1 << 10)` is one LED pattern and every pattern appears once.
`hour = mask >> 6` and `minute = mask & 0b111111` split the packed fields; a pattern is a real time only if `hour < 12 and minute < 60`, since 4 bits reach 15 and 6 bits reach 63.
1024 masks, each with an O(10) popcount: O(B * 2^B) with B = 10, constant time and O(1) extra space.
Binary Watch (LeetCode 401)
You will see how treating every LED pattern as one 10-bit number turns Binary Watch into a single loop over 1024 masks.
A binary watch shows the time with 10 LEDs. Four LEDs on the top encode the hour (0 to 11) and six LEDs on the bottom encode the minute (0 to 59); each LED is one bit, with the lowest bit on the right.
Given turnedOn, the number of LEDs that are lit, return every time the watch could be showing, in any order. Write the hour without a leading zero ("1:00", never "01:00") and the minute with exactly two digits ("10:02", never "10:2").
Worked Examples
turnedOn = 1["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]turnedOn = 9[]⚖️Formal Constraints & Bounds
0 <= turnedOn <= 10
Why It Works & Core Invariant
There are only 2^10 patterns of lit LEDs, and each is a number: test every mask, keep the ones with turnedOn bits, and decode the hour and minute fields with a shift and a mask, checking each field's range.
Real-World Scenario & Production Applications
Feature flags, permission sets and hardware status registers are all packed into integers, one bit per option. Enumerating every combination of a few flags (for example, to test each configuration) is a loop over range(1 << n), and decoding a register means shifting and masking its fields, then validating each one.
Subproblems & Recurrence Decomposition3 Phases
Leverage bitwise properties: x ^ x = 0 (cancellation), n & (n - 1) (clears lowest set bit), or right-shift induction dp[i] = dp[i >> 1] + (i & 1).
# Brian Kernighan Bit-Clearing:
# n & (n - 1) clears lowest set bit in O(1)Step-by-Step Execution Trace Table
Input turnedOn = 2: only masks with exactly two 1 bits pass the popcount check (45 of the 1024).
mask (binary, hour bits | minute bits) | hour = mask >> 6 | minute = mask & 0b111111 | hour < 12 and minute < 60? | Action |
|---|---|---|---|---|
0000 | 000011 = 3 | 0 | 3 | Yes | append "0:03" |
0000 | 000101 = 5 | 0 | 5 | Yes | append "0:05" |
| ... | ||||
0000 | 110000 = 48 | 0 | 48 | Yes | append "0:48" |
0001 | 000001 = 65 | 1 | 1 | Yes | append "1:01" |
| ... | ||||
1100 | 000000 = 768 | 12 | 0 | No (hour 12) | skip: 4 bits can spell 12 |
| End | 44 times returned |
| 1 | Every pattern of the 10 LEDs is one number from 0 to 1023: bit `i` is on when LED `i` is lit. |
| 2 | Keep a mask only when `bin(mask).count("1") == turnedOn`; its top 4 bits are the hour (`mask >> 6`) and its low 6 bits the minute (`mask & 0b111111`). |
| 3 | Loop `for mask in range(1 << 10)`, skip wrong popcounts, split into `hour, minute`, check the ranges, append `f"{hour}:{minute:02d}"`, return the list. |
| 4 | The trap: check `hour < 12 and minute < 60` after splitting, because 4 bits reach 15 and 6 bits reach 63. |
Target: Binary Watch (LeetCode 401). The 10 LEDs are the items, so the 1024 masks are every possible pattern of lit LEDs, each visited once.
Bit positions are independent channels processed simultaneously in 1 CPU cycle. n & (n - 1) clears lowest set bit; x ^ x = 0 cancels pairs.
while n > 0: n &= n - 1 (terminates after K cycles, K = set bits); or O(1) bitwise expressions.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
When a problem has only a handful of on/off items, every subset is just a number. Give item i bit i: a number whose bit i is 1 means "item i is chosen". The subsets of n items are then exactly the numbers 0 .. 2^n - 1, so one for mask in range(1 << n) loop visits each subset once, with no recursion and no duplicates. Binary Watch is the purest case: the 10 LEDs are the items, and a lit LED is a 1 bit.
🏟️ The Analogy: A Row of Light Switches
Ten switches on a wall are a 10-digit binary number. Counting from 0 to 1023 flips them through every possible pattern exactly once. Reading the pattern back is just as easy: the left 4 switches spell the hour in binary, the right 6 spell the minute.
🪄 The Mathematical Harmony / Magic Trick
for mask in range(1 << 10): # every pattern of 10 LEDs if bin(mask).count("1") != turnedOn: # popcount = lit LEDs continue hour, minute = mask >> 6, mask & 0b111111 if hour < 12 and minute < 60: # 4 bits reach 15, 6 bits reach 63 times.append(f"{hour}:{minute:02d}") mask >> 6 drops the 6 minute bits and leaves the hour; mask & 0b111111 keeps only the minute bits. The range check matters: a field of 4 bits can hold 12 to 15, which are not hours, and 6 bits can hold 60 to 63, which are not minutes.
💡 Summary
Small n plus "try every combination" means: loop over range(1 << n), read the subset from the bits, and validate each decoded field. masks with a 10-bit popcount each is a fixed amount of work.
Skipping the range check:
hour < 12 and minute < 60must follow the split. ForturnedOn = 2the mask1100 000000decodes to hour 12, and forturnedOn = 4the minute bits111100decode to 60; both are impossible times.Wrong field split: the hour is the top 4 bits,
mask >> 6; the minute is the low 6 bits,mask & 0b111111(63). Usingmask & 0b1111ormask >> 4mixes hour and minute LEDs.Formatting: the minute needs two digits (
f"{minute:02d}") and the hour none extra ("1:00", not"01:00").Forgetting
turnedOn = 0: the empty pattern, mask 0, is the valid time"0:00";range(1 << 10)starts at 0, so it is included.
4-Phase Thought Process Model
You will see how a senior engineer spots a bitmask enumeration and names its one real trap.
Pattern Recognition Signals
The 10-second spot
"10 LEDs", each on or off, and "return all possible times": a small, fixed set of on/off items where you must try every combination. With n = 10 there are only 1024 subsets, so each subset can simply be a number: Bitmask Subsets.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Bit i of mask is on exactly when LED i is lit, so range(1 << 10) visits each pattern once; a pattern is kept when bin(mask).count("1") == turnedOn and its decoded hour, minute = mask >> 6, mask & 0b111111 pass hour < 12 and minute < 60.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
if hour < 12 and minute < 60:: check each field after the split, because 4 bits reach 15 and 6 bits reach 63 (turnedOn = 2already produces hour 12).hour, minute = mask >> 6, mask & 0b111111: the hour is the top 4 bits, the minute the low 6; any other split mixes the two rows of LEDs.f"{hour}:{minute:02d}": two-digit minute, no leading zero on the hour.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd treat this as Bitmask Subsets. The watch has ten LEDs, so every pattern of lit LEDs is one number from 0 to 1023, with bit i on when LED i is lit. I loop over all 1024 masks and keep the ones whose popcount equals turnedOn. Then I decode: the top four bits, mask shifted right by six, are the hour, and the low six bits, mask and 63, are the minute. The trap is validation: four bits can spell up to 15 and six bits up to 63, so I keep a time only when the hour is below 12 and the minute below 60, and I format the minute with two digits. Each subset is one number, so every pattern is checked exactly once. It's 1024 masks with a 10-bit popcount each, a constant amount of work, and constant extra space beyond the answer.
So: 10 LEDs means 1024 masks; filter by popcount, split with >> 6 and & 0b111111, and range-check both fields.
Complexity & Mathematical Proof
O(B * 2^B), B = 10 LEDs
Look at the code: for mask in range(1 << 10) runs 2^B = 1024 times. Each iteration builds bin(mask) and counts its 1s in O(B), then does a shift, a mask and two comparisons in O(1). Total: O(B * 2^B) = about 10,000 basic steps, whatever turnedOn is.
O(1) extra, output not counted
Apart from the answer, the loop keeps mask, hour and minute and a short bin string of at most B + 2 characters: O(1) extra. The answer holds at most 720 times (12 hours x 60 minutes) and is not counted.
T = 2^B · O(B) = O(B · 2^B), B = 10
Look at the code: for mask in range(1 << 10) runs 2^B = 1024 times. Each iteration builds bin(mask) and counts its 1s in O(B), then does a shift, a mask and two comparisons in O(1). Total: O(B * 2^B) = about 10,000 basic steps, whatever turnedOn is.
Derivation Progression
2^B = 1024 iterations
for mask in range(1 << 10) visits every LED pattern once.
O(B) per mask
bin(mask).count("1") looks at each of the B bits.
O(1) per kept mask
One shift, one AND, two comparisons and a short format.
O(B · 2^B)
About 10,000 steps: a constant, independent of turnedOn.
Variable Definitions
Number of LEDs (bits), 10 on this watch
One pattern of lit LEDs, a number from 0 to 2^B - 1
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): mask, hour, minute, one bin string
At most 720 time strings (not counted)
Boundary Best / Worst Cases
: all masks are visited even when turnedOn is 0 or 10
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "4 LEDs for the hour, 6 for the minute", "every time the watch could show". A fixed, tiny set of on/off items (10 bits) and an "every combination" question: Bitmask Subsets, one number per subset.
turnedOn and exactly bits, so masks: constant work. Bitmask enumeration stays practical up to about items ( masks).
Decoded fields must be range-checked (hour 12-15 and minute 60-63 are representable but invalid). In production bit fields, the same rule holds for any packed register or flag word: validate every field after masking, since reserved or out-of-range values can be encoded.
Core Algorithmic State Invariants
Bit `i` of `mask` is on exactly when LED `i` is lit, so every number in `range(1 << 10)` is one LED pattern and every pattern appears once.
`hour = mask >> 6` and `minute = mask & 0b111111` split the packed fields; a pattern is a real time only if `hour < 12 and minute < 60`, since 4 bits reach 15 and 6 bits reach 63.
1024 masks, each with an O(10) popcount: O(B * 2^B) with B = 10, constant time and O(1) extra space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Every subset of n items is one number in range(1 << n) | for mask in range(1 << 10): | The 10 LEDs are the items, so the 1024 masks are every possible pattern of lit LEDs, each visited once. |
| Count the items in a subset with popcount | if bin(mask).count("1") != turnedOn:
continue | Only patterns with exactly turnedOn lit LEDs can be on the watch. |
| Decode the fields packed in the mask | hour, minute = mask >> 6, mask & 0b111111 | Shifting right by 6 drops the minute bits; masking with 0b111111 keeps only them. |
| Validate every decoded field | if hour < 12 and minute < 60: | Four bits can spell 12 to 15 and six bits 60 to 63; those patterns are not real times. |
| Build the answer in the required format | times.append(f"{hour}:{minute:02d}") | No leading zero on the hour, exactly two digits for the minute. |