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

Problem Summary ## Intuition ## Walkthrough: Understanding the Examples ## C++ Solution ## Python Solution ## JavaScript Solution ## Key Takeaways ## Final Thoughts 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. 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. 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. Example 1: `turnedOn = 1` If only one LED is on, the watch can only represent a single power of two. 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). 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. Templates let you quickly answer FAQs or store snippets for re-use. Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink. Hide child comments as well For further actions, you may consider blocking this person and/or reporting abuse COMMAND_BLOCK: 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 COMMAND_BLOCK: 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); } } } }; COMMAND_BLOCK: 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); } } } }; COMMAND_BLOCK: 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 COMMAND_BLOCK: 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 COMMAND_BLOCK: 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 COMMAND_BLOCK: /** * @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 COMMAND_BLOCK: /** * @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; }; COMMAND_BLOCK: /** * @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; }; - 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. - Maximum LEDs possible for a valid time: . - Since 9 LEDs is more than the maximum possible valid combination, it is impossible. - Result: [] (Empty list). - 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.