# 0401. Binary Watch

https://leetcode.com/problems/binary-watch

## Description

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom 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.leetcode.com/uploads/2021/04/08/binarywatch.jpg)

Given an integer `turnedOn` which represents the number of LEDs that are currently on, 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 be 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`

## ac

bit manipulation: n << i, n left shift i digits

```java
class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<String>();
        // edge cases
        if (num >= 10) return res;

        for (int h = 0; h <= num && h <= 4; h++) {
            // List<String> hours = binaryToStrings(h, 4);
            List<String> hours = new ArrayList<>();
            binaryToStrings(h, 4, 0, 0, hours);
            List<String> minutes = new ArrayList<>();
            binaryToStrings(num-h, 6, 0, 0, minutes);
            for (String hr : hours) {
                for (String min : minutes) {
                    if (min.length() < 2) min = "0" + min;
                    res.add(hr + ":" + min);
                }
            }
        }

        return res;
    }

    private void binaryToStrings(int n, int digits, int start, int curr, List<String> notes) {
        // exit
        if (n == 0) {  // all filled
            if (digits == 4 && curr < 12 || digits == 6 && curr < 60) notes.add("" + curr);
            return;
        }

        for (int i = start; i < digits; i++) {
            // if (((1 << i) & curr) > 0) continue; // this bit has value
            binaryToStrings(n-1, digits, i+1, curr + (1 << i), notes);
        }
    }
}
```
