401. Binary Watch LeetCode Solution

In this guide, you will get 401. Binary Watch LeetCode Solution with the best time and space complexity. The solution to Binary Watch problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Binary Watch solution in C++
Binary Watch solution in Java
Binary Watch solution in Python
Additional Resources

401. Binary Watch LeetCode Solution image

Problem Statement of Binary Watch

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”.

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

Complexity Analysis

Time Complexity: O(2^{10})
Space Complexity: O(2^{10})

401. Binary Watch LeetCode Solution in C++

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);
  }
};
/* code provided by PROGIEZ */

401. Binary Watch LeetCode Solution in Java

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);
  }
}
// code provided by PROGIEZ

401. Binary Watch LeetCode Solution in Python

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
 # code by PROGIEZ