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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Watch

Difficulty: Easy

Problem Description

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. 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, while the minute must consist of two digits and may contain a leading zero.

Key Insights

  • A binary watch consists of 4 bits for hours and 6 bits for minutes.
  • The total number of LEDs is 10, and the turnedOn parameter indicates how many of these are lit.
  • The valid hour range is 0-11 and the valid minute range is 0-59.
  • Generating all combinations of lit LEDs can be approached using backtracking to ensure all valid time combinations are explored.

Space and Time Complexity

Time Complexity: O(2^10) - Since we are generating combinations of 10 bits. Space Complexity: O(1) - The space used for the output list is dependent on the number of valid times but is not significant compared to the input size.

Solution

To solve the problem, we can use a backtracking approach to generate all possible combinations of LEDs that can be turned on. We will iterate through each possible combination and count the number of LEDs that are on. If the count matches turnedOn, we will check if the resulting time is valid (i.e., within the hour and minute limits) and format it correctly before adding it to our results.

Code Solutions

def readBinaryWatch(turnedOn):
    results = []
    
    # Helper function to count bits
    def count_bits(n):
        return bin(n).count('1')
    
    # Iterate through all possible combinations of hours (0-11) and minutes (0-59)
    for hour in range(12):
        for minute in range(60):
            if count_bits(hour) + count_bits(minute) == turnedOn:
                results.append(f"{hour}:{minute:02d}")  # Formatting minute with leading zero if necessary
    return results
← Back to All Questions