Binary Watch
More than twice downvotes.
The problem asks for all possible times that a binary watch can represent given a number of LEDs that are turned on. We can achieve this by iterating through all possible combinations of hours and minutes, checking the number of 1 bits (i.e., LEDs that are turned on) in their binary representation, and adding the valid combinations to our result.
Here’s the code to do this:


The function count_bits
counts the number of 1 bits in the binary representation of a number. We use this function to check if the sum of the 1 bits in the hour and minute parts is equal to n
. If it is, we add the corresponding time to our result.
This solution has a time complexity of O(1), as there are always 12 * 60 possible combinations of hours and minutes, and a space complexity of O(1), as we only use a constant amount of additional space.
Identifying Problem Isomorphism
“Binary Watch” can be approximately mapped to “Subsets”.
In “Binary Watch”, you are given a nonnegative integer n representing the number of LEDs that are currently on and asked to return all possible times the watch could represent. This problem can be interpreted as finding all subsets of a given size from a list of elements, where each element represents a LED light that contributes to a particular time. This aspect makes it analogous to the “Subsets” problem, which asks you to generate all possible subsets of a given set.
Both problems involve exploring all possibilities and generating subsets, so they share similarities in the strategies employed to solve them, such as recursion or iterative generation of combinations. However, in the “Binary Watch” problem, there is additional complexity in handling the time format and making sure generated combinations are valid times.
“Subsets” is simpler as it deals purely with generating combinations and does not require handling domainspecific constraints like in the “Binary Watch” problem.
Before attempting the “Binary Watch” problem (LeetCode 401), get a handle on bit manipulation, combinatorics and understanding how to handle binary representations in programming. Here are some simpler problems to build these skills:
“Number of 1 Bits” (LeetCode 191): Understand how to count the number of 1 bits in a number.
“Reverse Bits” (LeetCode 190): Get the basics of reversing bits.
“Bitwise AND of Numbers Range” (LeetCode 201): Get familiar with bitwise operations on a range of numbers.
“Subsets” (LeetCode 78): Understand basic combinatorics and how to generate all possible combinations.
“Combinations” (LeetCode 77): Understand how to generate combinations of certain size from a set of distinct integers.
“Single Number” (LeetCode 136): Learn how to use bitwise XOR operation to find the number that appears only once.
“Binary Number with Alternating Bits” (LeetCode 693): Understand how to check if the binary representation of a number has alternating bits.
“Power of Four” (LeetCode 342): Understand how to check if a number is a power of four using bit manipulation.
“Hamming Distance” (LeetCode 461): Learn how to calculate the Hamming distance between two integers.
“Counting Bits” (LeetCode 338): Learn how to count the number of 1 bits for all numbers from 0 to a given number.


Problem Classification
Bit Manipulation: This problem requires a clear understanding of binary representation of numbers. The LEDs on the watch represent bits in the binary representation of time, and the problem asks us to find all possible representations given a certain number of bits (LEDs) turned on. Bit manipulation operations are required to check the number of bits turned on for each possible time.
Backtracking/Brute Force: Given that the watch can only represent 12 hours and 60 minutes, a total of 720 different times, it is feasible to iterate through each possible time and check if it has the required number of LEDs turned on.
Combinatorial problem: Given the fact that the problem asks for all possible combinations of times given a number of LEDs turned on, this problem has a combinatorial nature.
This problem requires an understanding of binary representation and combinatorial enumeration.
Clarification Questions
What are the clarification questions we can ask about this problem?
Language Agnostic Coding Drills
Working with Binary Numbers: Understand how to work with binary numbers, and how to calculate the number of bits in a binary number. Python provides builtin functions for these operations (
bin
,int
,format
). Try converting integers to binary representation and vice versa. Count the number of set bits (1’s) in a binary number.Understanding Time Formatting: Familiarize yourself with string formatting in Python, especially zero padding (
str.zfill
). Learn how to format time into the required “HH:MM” format.Divmod function: Practice the use of the
divmod
function, which returns both the quotient and remainder when dividing two numbers. This function can be used to separate the hours and minutes in this problem.Iteration over all Possible Times: Iterate through all the possible hours (0 to 11) and minutes (0 to 59). Try to generate all possible combinations of hours and minutes, then format them into the required “HH:MM” format.
Using Combinations: Practice with the combinations function from Python’s itertools module. This function generates all possible combinations of a list with a given length. Try to generate all combinations of a list of integers.
Putting It All Together: Try to integrate all these parts together. For each possible time, calculate the number of set bits. If it equals the given number, format the time and add it to the result list.
The overall approach is to enumerate all the possible times (0:00 to 11:59), and for each time, calculate the binary representation of the time, counting the number of 1’s (set bits). If the number of set bits equals the number of LEDs turned on, then add this time to the result list. After enumerating all possible times, return the result list.
Targeted Drills in Python
1. Working with Binary Numbers:
This exercise is about converting integers to binary and vice versa, as well as counting the number of set bits in a binary number.


2. Understanding Time Formatting:
In this drill, you will learn to format time into “HH:MM” format and understand zero padding.


3. Divmod function:
This exercise is about using the divmod
function to separate hours and minutes.


4. Iteration over all Possible Times:
This drill is about generating all possible combinations of hours and minutes.


5. Using Combinations:
In this exercise, you will generate all combinations of a list of integers.


6. Putting It All Together:
Finally, we put all these pieces together to solve the problem. This drill is left as a challenge. Try to use all the skills you practiced in the above drills to implement the solution for the problem.