Skip to content

401. Binary Watch 👎

Approach 1: DFS

  • Time: $O(2^{10})$
  • Space: $O(2^{10})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  vector<string> readBinaryWatch(int turnedOn) {
    vector<string> ans;
    dfs(turnedOn, 0, 0, 0, ans);
    return ans;
  }

 private:
  static constexpr int hours[4] = {1, 2, 4, 8};
  static constexpr int minutes[6] = {1, 2, 4, 8, 16, 32};

  void dfs(int turnedOn, int s, int h, int m, vector<string>& ans) {
    if (turnedOn == 0) {
      string time = to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m);
      ans.push_back(time);
      return;
    }

    for (int i = s; i < 4 + 6; ++i)
      if (i < 4 && h + hours[i] < 12)
        dfs(turnedOn - 1, i + 1, h + hours[i], m, ans);
      else if (i >= 4 && m + minutes[i - 4] < 60)
        dfs(turnedOn - 1, i + 1, h, m + minutes[i - 4], ans);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public List<String> readBinaryWatch(int turnedOn) {
    List<String> ans = new ArrayList<>();
    dfs(turnedOn, 0, 0, 0, ans);
    return ans;
  }

  private int[] hours = new int[] {1, 2, 4, 8};
  private int[] minutes = new int[] {1, 2, 4, 8, 16, 32};

  private void dfs(int turnedOn, int s, int h, int m, List<String> ans) {
    if (turnedOn == 0) {
      final String time = String.valueOf(h) + ":" + (m < 10 ? "0" : "") + String.valueOf(m);
      ans.add(time);
      return;
    }

    for (int i = s; i < hours.length + minutes.length; ++i)
      if (i < 4 && h + hours[i] < 12)
        dfs(turnedOn - 1, i + 1, h + hours[i], m, ans);
      else if (i >= 4 && m + minutes[i - 4] < 60)
        dfs(turnedOn - 1, i + 1, h, m + minutes[i - 4], ans);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def readBinaryWatch(self, turnedOn: int) -> list[str]:
    ans = []
    hours = [1, 2, 4, 8]
    minutes = [1, 2, 4, 8, 16, 32]

    def dfs(turnedOn: int, s: int, h: int, m: int) -> None:
      if turnedOn == 0:
        time = str(h) + ":" + (str(m).zfill(2))
        ans.append(time)
        return

      for i in range(s, len(hours) + len(minutes)):
        if i < 4 and h + hours[i] < 12:
          dfs(turnedOn - 1, i + 1, h + hours[i], m)
        elif i >= 4 and m + minutes[i - 4] < 60:
          dfs(turnedOn - 1, i + 1, h, m + minutes[i - 4])

    dfs(turnedOn, 0, 0, 0)
    return ans

Approach 2: Bit

  • Time: $O(12 \cdot 60)$
  • Space: $O(12 \cdot 60)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  vector<string> readBinaryWatch(int turnedOn) {
    vector<string> ans;

    for (unsigned h = 0; h < 12; ++h)
      for (unsigned m = 0; m < 60; ++m)
        if (popcount(h << 6 | m) == turnedOn)
          ans.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public List<String> readBinaryWatch(int turnedOn) {
    List<String> ans = new LinkedList<>();

    for (int h = 0; h < 12; ++h)
      for (int m = 0; m < 60; ++m)
        if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn)
          ans.add(h + (m < 10 ? ":0" : ":") + m);

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def readBinaryWatch(self, turnedOn: int) -> list[str]:
    ans = []

    for h in range(12):
      for m in range(60):
        if h.bit_count() + m.bit_count() == turnedOn:
          ans.append(f'{h}:{m:02d}')

    return ans