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 num) {
    vector<string> ans;
    dfs(num, 0, 0, 0, ans);
    return ans;
  }

 private:
  const vector<int> hours{1, 2, 4, 8};
  const vector<int> minutes{1, 2, 4, 8, 16, 32};

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

    for (int i = s; i < hours.size() + minutes.size(); ++i)
      if (i < 4 && h + hours[i] < 12)
        dfs(n - 1, i + 1, h + hours[i], m, ans);
      else if (i >= 4 && m + minutes[i - 4] < 60)
        dfs(n - 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 num) {
    List<String> ans = new ArrayList<>();
    dfs(num, 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 n, int s, int h, int m, List<String> ans) {
    if (n == 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(n - 1, i + 1, h + hours[i], m, ans);
      else if (i >= 4 && m + minutes[i - 4] < 60)
        dfs(n - 1, i + 1, h, m + minutes[i - 4], 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 num) {
    vector<string> ans;

    for (int h = 0; h < 12; ++h)
      for (int m = 0; m < 60; ++m)
        if (__builtin_popcount(h << 6 | m) == num)
          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 num) {
    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) == num)
          ans.add(h + (m < 10 ? ":0" : ":") + m);

    return ans;
  }
}