What is the time complexity of Binary Watch?

The optimal solution has a time complexity of O(1).

What data structures are used to solve Binary Watch?

This problem uses Backtracking, Bit Manipulation. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Binary Watch?

Insight 1: The hour can range from 0 to 11, and the minute can range from 0 to 59. We can iterate through all possible hour and minute combinations. Insight 2: For each hour and minute combination, we can count the number of set bits (1s) in their binary representations using built-in functions or bit manipulation.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Binary Watch - LeetCode 401 Solution

Binary Watch - Complete Solution Guide

Binary Watch is LeetCode problem 401, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Framing

Binary Watch is a Easy LeetCode problem that rewards careful tracing, edge-case handling, and a clear grasp of Backtracking and Bit Manipulation. The best solutions usually explain why the chosen invariant holds before they optimize for time or space.

Quick Example Mindset

A useful way to test Binary Watch is to start with a tiny input that exposes the boundary conditions, then run the same logic on a slightly larger case to verify the backtracking behavior and the bit manipulation interaction. That second pass is where off-by-one mistakes and missing updates usually appear.

Problem Statement

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

Detailed Explanation

The problem asks us to simulate a binary watch, which displays the time using LEDs. Four LEDs represent the hours (0-11), and six LEDs represent the minutes (0-59). Given a number `turnedOn`, representing the number of lit LEDs, we need to find all possible valid times the watch can display and return them as a list of strings in the format "HH:MM". For example, if `turnedOn` is 1, one LED is lit. This could represent 0:01, 0:02, 0:04, 0:08, 0:16, 0:32, 1:00, 2:00, 4:00, or 8:00.

Solution Approach

The provided solutions use a brute-force approach. They iterate through all possible hour values (0-11) and all possible minute values (0-59). For each combination, they calculate the number of lit LEDs needed to represent the current hour and minute. If the total number of lit LEDs matches the input `turnedOn`, the combination is considered a valid time. The solutions then format the valid hour and minute into a string of the form "HH:MM", padding the minute with a leading zero if it's less than 10, and adds it to the list of results.

Step-by-Step Algorithm

Step 1: Initialize an empty list called `ans` to store the valid times.
Step 2: Iterate through all possible hour values from 0 to 11 (inclusive).
Step 3: Iterate through all possible minute values from 0 to 59 (inclusive).
Step 4: Calculate the number of set bits (lit LEDs) in the binary representation of the current hour.
Step 5: Calculate the number of set bits (lit LEDs) in the binary representation of the current minute.
Step 6: Check if the sum of set bits in the hour and minute equals the input `turnedOn`.
Step 7: If the sum equals `turnedOn`, format the hour and minute into a string "HH:MM". Ensure the minute has two digits (e.g., "05" instead of "5").
Step 8: Add the formatted time string to the `ans` list.
Step 9: After iterating through all possible hour and minute values, return the `ans` list.

Key Insights

Insight 1: The hour can range from 0 to 11, and the minute can range from 0 to 59. We can iterate through all possible hour and minute combinations.
Insight 2: For each hour and minute combination, we can count the number of set bits (1s) in their binary representations using built-in functions or bit manipulation.
Insight 3: If the sum of set bits in the hour and minute matches the input `turnedOn`, we format the hour and minute into a string "HH:MM" and add it to the result list. Ensure the minute part is always two digits, padding with a leading zero if necessary.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Topics

This problem involves: Backtracking, Bit Manipulation.

Study Paths

Continue from this problem into the surrounding topic and company clusters to compare how the same pattern appears in other interview settings.

Related topics: Backtracking, Bit Manipulation

Frequently Asked Questions

How do I avoid duplicate solutions in backtracking?

Sort the input first, then skip consecutive duplicates at the same recursion level: if (i > start && nums[i] == nums[i-1]) continue. For permutations, use a visited array or swap-based approach. Always consider if order matters (permutations vs combinations).

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

Binary Watch | LeetCode 401

Easy

Backtracking Bit Manipulation

Study Path

Browse topics

Continue through the pattern hub for deeper coverage and neighboring problem variants.

Backtracking Bit Manipulation

Company Signals

Browse companies

Review the companies that ask this problem and move into adjacent interview sets.

No company matches yet.

Time: O(1)Space: O(1)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    String hour = String.valueOf(h);
                    String minute = String.format("%02d", m);
                    result.add(hour + ":" + minute);
                }
            }
        }
        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 401: Binary Watch - Detailed explanation and solution approaches.

Topics

Backtracking Bit Manipulation

Stats

Difficulty:Easy

Languages:4

Problem #:401

Problem Explanation

🧭

Next Steps

Use this problem as a starting point, then move into adjacent patterns and company sets to reinforce the same idea in different contexts.

Topic hub

Study neighboring problems by pattern and difficulty.

Company hub

See where this problem appears in interview loops.

Pattern guides

Read deeper walkthroughs of the algorithm family.

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize an empty list called `ans` to store the valid times.
2
Step 2: Iterate through all possible hour values from 0 to 11 (inclusive).
3
Step 3: Iterate through all possible minute values from 0 to 59 (inclusive).
4
Step 4: Calculate the number of set bits (lit LEDs) in the binary representation of the current hour.
5
Step 5: Calculate the number of set bits (lit LEDs) in the binary representation of the current minute.
6
Step 6: Check if the sum of set bits in the hour and minute equals the input `turnedOn`.
7
Step 7: If the sum equals `turnedOn`, format the hour and minute into a string "HH:MM". Ensure the minute has two digits (e.g., "05" instead of "5").
8
Step 8: Add the formatted time string to the `ans` list.
9
Step 9: After iterating through all possible hour and minute values, return the `ans` list.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(1)

⚡ Constant time - Super fast! Same speed regardless of input size.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(1) because the outer loop iterates a maximum of 12 times (hours) and the inner loop iterates a maximum of 60 times (minutes). This is a fixed number of iterations, regardless of the input `turnedOn`. The space complexity is O(1) because the size of the output list is bounded by a constant. There is a maximum number of possible combinations of hours and minutes for a given `turnedOn` value. Even in the worst-case scenario where all combinations are valid, the number of combinations is limited due to the constraints on the hour and minute values.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Backtracking

We can use a backtracking approach where we represent the LEDs as an array of booleans. We can recursively try turning on each LED and checking if the resulting hour and minute are valid and if the number of turned-on LEDs matches the input `turnedOn`.

Time: O(C(10, turnedOn)) where C is the combination function. This is because we have to explore all possible combinations of turning on `turnedOn` LEDs out of a total of 10 LEDs.Space: O(10) for the boolean array representing LEDs and O(number of valid combinations) to store the result.

Trade-offs: Backtracking can be more intuitive for some, but due to the small input range, the brute-force approach is faster in practice. Brute force also avoids the overhead of recursion.

✨

Key Insights

1Insight 1: The hour can range from 0 to 11, and the minute can range from 0 to 59. We can iterate through all possible hour and minute combinations.
2Insight 2: For each hour and minute combination, we can count the number of set bits (1s) in their binary representations using built-in functions or bit manipulation.
3Insight 3: If the sum of set bits in the hour and minute matches the input `turnedOn`, we format the hour and minute into a string "HH:MM" and add it to the result list. Ensure the minute part is always two digits, padding with a leading zero if necessary.

📚

Key Terms Explained

For Students

Edge Cases

Edge case 1: `turnedOn` is 0. The only possible time is "0:00". The code correctly handles this since the loops will iterate through h=0 and m=0, and `bin(0).count('1') + bin(0).count('1') == 0`.
Edge case 2: `turnedOn` is greater than 10. This will result in an empty list because the total number of LEDs is fixed at 10 (4 for hours, 6 for minutes), and it's impossible to turn on more LEDs than available. The code handles this correctly because no combination of hours and minutes will satisfy the condition `bin(h).count('1') + bin(m).count('1') == turnedOn`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not padding the minute with a leading zero when it's a single digit (e.g., displaying "1:5" instead of "1:05"). The solutions use string formatting (e.g., `f"{h}:{m:02d}"` in Python, `String.format("%02d", m)` in Java) to ensure correct formatting.

✗Common mistake 2: Not handling invalid hour or minute values (e.g., hour > 11 or minute > 59). The loops in the solution inherently ensure that the hour and minute values are within valid ranges.

✗Common mistake 3: Assuming a certain order of LEDs for hours and minutes. The problem description defines this implicitly.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Embedded systems with limited resources often use binary representations for time, date, or other numerical values. This problem demonstrates a simple interface to interpret such binary data.

🏦Real-world scenario 2: Similar logic can be applied to LED displays for various devices (e.g., timers, counters) where the number of lit LEDs represents a certain value.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Backtracking = DFS + pruning. The key is identifying when to backtrack. Always restore state after recursion.

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 12, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 21

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

❓

Frequently Asked Questions

How do I avoid duplicate solutions in backtracking?

What should I learn from easy problems?

What is the importance of time and space complexity analysis?

What is the optimal approach for "Binary Watch"?

For this easy-level Backtracking problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether bit manipulation techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?