# Binary Watch
**Difficulty:** EASY
[External](https://leetcode.com/problems/binary-watch)
Canonical: https://scaleengineer.com/dsa/problems/binary-watch
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## Problem
A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

* For example, the below binary watch reads `"4:51"`.

![](https://assets.glich.co/dsa/binary-watch/image0.jpg)

Given an integer `turnedOn` which represents the number of LEDs that are currently on (ignoring the PM), return _all possible times the watch could represent_. You may return the answer in **any order**.

The hour must not contain a leading zero.

* For example, `"01:00"` is not valid. It should be `"1:00"`.

The minute must consist of two digits and may contain a leading zero.

* For example, `"10:2"` is not valid. It should be `"10:02"`.

**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"]

**Example 2:**

**Input:** turnedOn = 9
**Output:** []

**Constraints:**

* `0 <= turnedOn <= 10`

# Approaches
## Brute-Force Iteration Over Time
This approach involves checking every possible time from 0:00 to 11:59. For each time, we count the number of 'on' LEDs (set bits) in the binary representation of the hour and the minute. If the total count matches the given `turnedOn` number, the time is considered valid and added to the result list.
**Time:** O(1). The loops run a fixed number of times (12 hours * 60 minutes = 720 iterations). The operations inside the loop, like `bitCount` and string formatting, are constant time. While technically O(1), it's a fixed, relatively high number of operations. · **Space:** O(1). The space required for the output list is bounded by a constant, as there's a fixed maximum number of possible times. No other significant space is used.
**Pros:** Very simple to understand and implement.; Requires no complex data structures or algorithms.
**Cons:** Performs a fixed number of 720 iterations, regardless of the `turnedOn` value, making it less efficient for inputs where few combinations are possible (e.g., `turnedOn = 0` or `turnedOn = 10`).
### Explanation
The most straightforward way to solve this problem is to simulate a clock and check every minute of a 12-hour cycle. We can use nested loops to iterate through all possible hours (`h`) from 0 to 11 and all possible minutes (`m`) from 0 to 59.

In each iteration, we need to determine how many LEDs would be on for that specific time `h:m`. This is equivalent to counting the number of set bits (1s) in the binary representations of `h` and `m`. Most programming languages provide a built-in function for this, such as `Integer.bitCount()` in Java.

The total number of 'on' LEDs is the sum of bits for the hour and the minute: `Integer.bitCount(h) + Integer.bitCount(m)`.

We compare this sum with the input `turnedOn`. If they are equal, we have found a valid time. We then format this time into the required `"H:MM"` string format. For example, if `h=4` and `m=5`, the string should be `"4:05"`. This formatted string is then added to our list of results.

After checking all 12 * 60 = 720 possible times, the list containing all valid time strings is returned.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();
        // Iterate through all possible hours (0-11)
        for (int h = 0; h < 12; h++) {
            // Iterate through all possible minutes (0-59)
            for (int m = 0; m < 60; m++) {
                // Count the number of set bits for hour and minute
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    // Format the time and add to the result list
                    result.add(String.format("%d:%02d", h, m));
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result` to store the valid times.
- Loop for hour `h` from 0 to 11.
-  Inside the hour loop, loop for minute `m` from 0 to 59.
-   Calculate the number of set bits for the current hour `h` and minute `m` using `Integer.bitCount(h) + Integer.bitCount(m)`.
-   If the total number of set bits equals `turnedOn`:
    -    Format the time as a string `h:mm`. The minute part must be two digits, so pad with a leading zero if necessary (e.g., `7` becomes `07`).
    -    Add the formatted string to the `result` list.
- After the loops complete, return the `result` list.

## Iterating through LED Combinations
This approach is more optimized. Instead of checking every possible time, we only construct the times that can be formed with the given number of `turnedOn` LEDs. We iterate through all possible ways to distribute the `turnedOn` LEDs between the hour (4 LEDs) and minute (6 LEDs) sections and generate the corresponding valid times.
**Time:** O(1). The input `turnedOn` is bounded (0-10), so the problem space is fixed. However, this approach is computationally superior to brute-force because the number of operations is much smaller. Instead of 720 checks, it's a sum over combinations, e.g., for `turnedOn=5`, it's roughly `C(4,2)*C(6,3) = 6*20 = 120` combinations plus generation time. · **Space:** O(1). We use lists to store intermediate hours and minutes, but their sizes are bounded by small constants (max size for hours is C(4,2)=6, for minutes is C(6,3)=20). The final result list is also bounded.
**Pros:** More efficient than brute-force as it explores a much smaller and more relevant search space.; The number of computations is directly related to the number of valid combinations, not a fixed large number.
**Cons:** Slightly more complex to implement than the simple brute-force iteration.; Involves creating and managing intermediate data structures (lists for hours and minutes).
### Explanation
A more efficient method is to think about the problem in terms of combinations. We have a total of `turnedOn` LEDs to distribute among the 4 hour LEDs and 6 minute LEDs.

Let `h_leds` be the number of LEDs turned on for the hour and `m_leds` be the number for the minute. We know that `h_leds + m_leds = turnedOn`. We can iterate through all possible values for `h_leds` (from 0 up to `turnedOn`). For each `h_leds`, `m_leds` is determined.

We must respect the physical constraints of the watch: `0 <= h_leds <= 4` and `0 <= m_leds <= 6`. So, for each `h_leds` we consider, we first check if this distribution is possible.

If the distribution is valid, we perform two sub-tasks:
1.  Find all possible hour values (from 0 to 11) that can be formed with exactly `h_leds` LEDs on.
2.  Find all possible minute values (from 0 to 59) that can be formed with exactly `m_leds` LEDs on.

We can generate these lists of hours and minutes by iterating from 0-11 and 0-59 respectively, and checking their bit counts. Once we have the list of possible hours and the list of possible minutes, we find their Cartesian product. Every hour from the first list is combined with every minute from the second list to form a valid time. Each resulting time is formatted and added to our final list.

This method significantly reduces the number of combinations to check compared to the brute-force approach, as it directly constructs valid possibilities rather than searching for them in a large space.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();
        // Iterate through all possible numbers of LEDs for the hour part (0 to 4)
        for (int h_leds = 0; h_leds <= 4; h_leds++) {
            // The remaining LEDs are for the minute part (0 to 6)
            int m_leds = turnedOn - h_leds;
            if (m_leds >= 0 && m_leds <= 6) {
                // Generate possible hours
                List<Integer> hours = new ArrayList<>();
                for (int h = 0; h < 12; h++) {
                    if (Integer.bitCount(h) == h_leds) {
                        hours.add(h);
                    }
                }

                // Generate possible minutes
                List<Integer> minutes = new ArrayList<>();
                for (int m = 0; m < 60; m++) {
                    if (Integer.bitCount(m) == m_leds) {
                        minutes.add(m);
                    }
                }

                // Combine hours and minutes to form times
                for (int h : hours) {
                    for (int m : minutes) {
                        result.add(String.format("%d:%02d", h, m));
                    }
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- Loop for `h_leds` (number of hour LEDs) from 0 to `turnedOn`.
-  Calculate `m_leds = turnedOn - h_leds`.
-  If `h_leds > 4` or `m_leds > 6`, it's an invalid distribution, so skip to the next iteration.
-  Generate a list `hours` containing all integers from 0-11 that have exactly `h_leds` set bits.
-  Generate a list `minutes` containing all integers from 0-59 that have exactly `m_leds` set bits.
-  Use nested loops to iterate through each `h` in `hours` and each `m` in `minutes`.
-   For each pair `(h, m)`, format the time as a string `h:mm` and add it to `result`.
- Return `result`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  vector<string> readBinaryWatch(int turnedOn) {
    vector<string> ans;
    for (int i = 0; i < 12; ++i) {
      for (int j = 0; j < 60; ++j) {
        if (__builtin_popcount(i) + __builtin_popcount(j) == turnedOn) {
          ans.push_back(to_string(i) + ":" + (j < 10 ? "0" : "") +
                        to_string(j));
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]: return ['{:d}:{:02d}' . format(
        i, j) for i in range(12) for j in range(60) if (bin(i) + bin(j)). count('1') == turnedOn]

```