We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Watch

Number: 401

Difficulty: Easy

Paid? No

Companies: Uber, Google

Problem Description

A binary watch has 4 LEDs to represent the hours (0-11) and 6 LEDs to represent the minutes (0-59). Each LED represents a binary digit (0 or 1) where the least significant bit is on the right. Given an integer turnedOn representing the number of LEDs that are currently on, return all possible times the watch could represent. Note that the hour should not have a leading zero (e.g., "01:00" is invalid) and the minute must always be in a two-digit format (e.g., "10:2" is invalid).

Key Insights

  • The watch is split into hours (0-11) and minutes (0-59), totaling 10 LEDs.
  • Use bit manipulation (or counting bits from integer binary representations) to determine how many LEDs are on.
  • A brute-force solution is efficient enough since the total number of combinations (12 hours * 60 minutes = 720) is fixed.
  • Format hours without a leading zero and minutes with a two-digit format.

Space and Time Complexity

Time Complexity: O(1) – A constant 720 iterations maximum (12 hours x 60 minutes). Space Complexity: O(1) – Aside from the output, only a constant amount of space is used.

Solution

The algorithm iterates through all possible hour and minute combinations. For each combination, it counts the number of 1s in the binary representation of the hour and the minute. If the total matches turnedOn, it formats the time string (ensuring the minute is a two-digit number) and adds it to the result list. This utilizes bit manipulation for counting and simple string formatting for the output.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with detailed line-by-line comments.

def readBinaryWatch(turnedOn):
    results = []  # This list will store all valid time strings.
    
    # Iterate through all possible hour values (0 - 11)
    for hour in range(12):
        # Iterate through all possible minute values (0 - 59)
        for minute in range(60):
            # Count the number of LEDs turned on by adding bit counts from hour and minute
            if bin(hour).count("1") + bin(minute).count("1") == turnedOn:
                # Format time as "hour:minute" where minute is two digits (e.g., 01, 02)
                results.append(f"{hour}:{minute:02d}")
    
    return results

# Example usage:
print(readBinaryWatch(1))
← Back to All Questions