Binary Watch

Naive Approach

The most straightforward approach is to iterate through all possible hour and minute combinations and check if the number of set bits (1s) in their binary representations equals the given turnedOn value.

1. Iterate through all possible hours (0-11) and minutes (0-59).
2. For each hour and minute combination, count the number of set bits in their binary representations.
3. If the total number of set bits equals turnedOn, format the hour and minute into a string "H" and add it to the result list.

Code (Python)

def readBinaryWatch_naive(turnedOn: int) -> list[str]:
    result = []
    for hour in range(12):
        for minute in range(60):
            if bin(hour).count('1') + bin(minute).count('1') == turnedOn:
                result.append(f"{hour}:{minute:02}")
    return result

Big O Analysis

• Time Complexity: O(1). The outer loop iterates 12 times, and the inner loop iterates 60 times. Therefore, the total number of iterations is fixed (12 * 60 = 720), making the time complexity constant.
• Space Complexity: O(k), where k is the number of valid times. In the worst case, the number of valid times could be significant, but it's still bounded, hence it is technically O(1) as well because the result is bounded.

Optimal Approach

This is essentially the same as the brute force solution since it's hard to optimize much further.

Edge Cases

• turnedOn is less than 0 or greater than 10. If turnedOn is greater than 10, there are no possible combinations.
• The hour is not a valid hour (0-11).
• The minute is not a valid minute (0-59).

Code (Python)

def count_bits(n: int) -> int:
    count = 0
    while n > 0:
        n &= (n - 1)
        count += 1
    return count

def readBinaryWatch(turnedOn: int) -> list[str]:
    result = []
    for hour in range(12):
        for minute in range(60):
            if count_bits(hour) + count_bits(minute) == turnedOn:
                result.append(f"{hour}:{minute:02}")
    return result

Big O Analysis

• Time Complexity: O(1). We iterate through all possible hour and minute combinations (12 * 60 = 720), which is constant time.
• Space Complexity: O(k), where k is the number of valid times. The space is used to store the result list. As k is bounded, space complexity is effectively O(1).