DEV Community

Cover image for ⌚ Beginner-Friendly Guide 'Binary Watch' - Problem 401 (C++, Python, JavaScript)
Om Shree
Om Shree

Posted on

⌚ Beginner-Friendly Guide 'Binary Watch' - Problem 401 (C++, Python, JavaScript)

#programming #cpp #python #javascript

Ever wondered how digital devices represent time using nothing but ones and zeros? This problem invites you to decode a binary watch, where LEDs represent powers of two for both hours and minutes. It is a fantastic way to practice how we can combine different possibilities to reach a specific target.

Problem Summary

You're given:
An integer turnedOn, which represents the total number of LEDs currently glowing on a binary watch.

Your goal:
Return a list of all possible valid times the watch could be showing. You must ensure hours are between 0 and 11, and minutes are between 0 and 59.

Intuition

The watch has 10 LEDs in total: 4 for hours () and 6 for minutes (). Since the total number of possible times is small (only combinations), we can use a Backtracking (DFS) approach to pick which LEDs to turn on.

The core logic revolves around iterating through the 10 available LEDs. For each LED, we decide to "turn it on" and subtract 1 from our turnedOn count. We keep track of the current hour and minute values, ensuring they never exceed their respective limits. Once the count reaches zero, we format the resulting time and add it to our list.

Walkthrough: Understanding the Examples

Example 1: `turnedOn = 1`
If only one LED is on, the watch can only represent a single power of two.

  • If a minute LED is on: It could be 0:01, 0:02, 0:04, 0:08, 0:16, or 0:32.
  • If an hour LED is on: It could be 1:00, 2:00, 4:00, or 8:00.
  • Result: A list of all 10 individual time stamps.

Example 2: `turnedOn = 9`
The maximum possible value for hours is 11 (requires 3 LEDs: 8+2+1) and for minutes is 59 (requires 5 LEDs: 32+16+8+2+1).

  • Maximum LEDs possible for a valid time: .
  • Since 9 LEDs is more than the maximum possible valid combination, it is impossible.
  • Result: [] (Empty list).

C++ Solution 

class Solution {
 public:
  vector<string> readBinaryWatch(int turnedOn) {
    vector<string> ans;
    // Start DFS with turnedOn LEDs remaining, starting at index 0, hour 0, minute 0
    dfs(turnedOn, 0, 0, 0, ans);
    return ans;
  }

 private:
  const int hours[4] = {1, 2, 4, 8};
  const 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 < 10; ++i) {
      if (i < 4) { // Hour LEDs (indices 0-3)
        if (h + hours[i] < 12)
          dfs(turnedOn - 1, i + 1, h + hours[i], m, ans);
      } else { // Minute LEDs (indices 4-9)
        if (m + minutes[i - 4] < 60)
          dfs(turnedOn - 1, i + 1, h, m + minutes[i - 4], ans);
      }
    }
  }
};
Enter fullscreen mode Exit fullscreen mode

Python Solution 

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        ans = []
        hours = [1, 2, 4, 8]
        minutes = [1, 2, 4, 8, 16, 32]

        def dfs(remaining, start_idx, h, m):
            if remaining == 0:
                # Format: No leading zero for hours, two digits for minutes
                ans.append(f"{h}:{m:02d}")
                return

            for i in range(start_idx, 10):
                if i < 4:  # Hour LEDs
                    if h + hours[i] < 12:
                        dfs(remaining - 1, i + 1, h + hours[i], m)
                else:  # Minute LEDs
                    if m + minutes[i - 4] < 60:
                        dfs(remaining - 1, i + 1, h, m + minutes[i - 4])

        dfs(turnedOn, 0, 0, 0)
        return ans
Enter fullscreen mode Exit fullscreen mode

JavaScript Solution 

/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function(turnedOn) {
    const ans = [];
    const hours = [1, 2, 4, 8];
    const minutes = [1, 2, 4, 8, 16, 32];

    const dfs = (remaining, startIdx, h, m) => {
        if (remaining === 0) {
            const formattedMin = m < 10 ? "0" + m : m;
            ans.push(h + ":" + formattedMin);
            return;
        }

        for (let i = startIdx; i < 10; i++) {
            if (i < 4) { // Hour LEDs
                if (h + hours[i] < 12) {
                    dfs(remaining - 1, i + 1, h + hours[i], m);
                }
            } else { // Minute LEDs
                if (m + minutes[i - 4] < 60) {
                    dfs(remaining - 1, i + 1, h, m + minutes[i - 4]);
                }
            }
        }
    };

    dfs(turnedOn, 0, 0, 0);
    return ans;
};
Enter fullscreen mode Exit fullscreen mode

Key Takeaways

  • Combinatorial Search: Backtracking is the perfect tool when you need to explore combinations of items to reach a fixed sum or count.
  • State Management: By passing h (hours) and m (minutes) through the recursion, we maintain the "state" of our watch without needing to undo changes manually.
  • Constraint Checking: Always validate boundaries (hours < 12, minutes < 60) before committing to a recursive path to save computation time.

Final Thoughts

This problem is a classic example of how hardware interacts with software logic. While it appears simple, it tests your ability to handle multiple constraints and format data correctly. In the real world, similar bit-manipulation and combinatorial logic are used in embedded systems, low-level driver development, and even when designing efficient network protocols where every bit counts.

Top comments (0)