algoadvance

A binary watch has 4 LEDs on the top to represent the hours (0-11), and the 6 LEDs on the bottom to represent the minutes (0-59). Each LED has a binary value (1, 2, 4, 8, 16, 32), and they are read by summing the values of the LEDs that are lit.

Given a non-negative integer num which represents the number of LEDs that are currently on, return all possible times the watch could represent.

The order of output does not matter.

Clarifying Questions

1. Can num be larger than 10?
   • No, because there are only 10 LEDs (4 for hours and 6 for minutes).
2. Should the times be formatted in any specific way?
   • Yes, times should be formatted in “h:mm” format, where h is hours (0-11) and mm is minutes (00-59).
3. Can num be 0?
   • Yes, and the only time then would be “0:00”.

Strategy

1. Binary Representation: Use the binary representation to determine the number of LEDs lit for both hours and minutes.
2. Iteration: Iterate over all possible combinations of hours (0-11) and minutes (0-59) to check the count of LEDs.
3. Combination Checking: Use a helper function to count the number of 1’s in the binary representation (bin(x).count('1')).
4. Result Accumulation: Collect all valid times in a result list and return it.

Code

def readBinaryWatch(num: int):
    def bit_count(x):
        return bin(x).count('1')
    
    times = []
    for h in range(12):
        for m in range(60):
            if bit_count(h) + bit_count(m) == num:
                times.append(f"{h}:{m:02d}")
    return times

# Example usage:
# num = 1
# print(readBinaryWatch(num))

Time Complexity

• Iteration through Hours and Minutes: We iterate through 12 hours and 60 minutes, making it a total of 720 iterations.
• Binary Count Calculation: Checking the binary count for each combination is O(1) since the max number is 12 (hours) and 59 (minutes).
• Overall Complexity: O(720 * 2) which simplifies to O(720) or O(1) since 720 is a constant.

This approach provides an efficient and concise solution to determining all possible times for a given number of LEDs lit on a binary watch.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?