Jobs

Interviews

Discussions

Binary Watch

Easy

Asked by:

50 views

Topics:

Bit ManipulationRecursion

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 example, "01:00" is not valid. It should be "1:00".

The minute must consist of two digits and may contain a leading zero.

For example, "10:2" is not valid. It should be "10:02".

Example 1:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Example 2:

Input: turnedOn = 9
Output: []

Constraints:

0 <= turnedOn <= 10

Try coding it in LeetCode

Binary Watch

Easy

Asked by:

50 views

Topics:

Bit ManipulationRecursion

For example, the below binary watch reads "4:51".

The hour must not contain a leading zero.

For example, "01:00" is not valid. It should be "1:00".

The minute must consist of two digits and may contain a leading zero.

For example, "10:2" is not valid. It should be "10:02".

Example 1:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Example 2:

Input: turnedOn = 9
Output: []

Constraints:

0 <= turnedOn <= 10

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The problem states we need to represent hours and minutes. Can you clarify the valid range for the input 'turnedOn' (number of lit LEDs)? For example, can it be negative, zero, or greater than the maximum number of LEDs (10)?
What should the function return if the given 'turnedOn' value cannot represent any valid time (e.g., too many LEDs to represent a valid hour and minute)? Should I return an empty list, null, or throw an exception?
Are the hours represented in 12-hour format (1-12) or 24-hour format (0-23)? Minutes should be between 0-59, correct?
Is there any specific order required for the output strings in the list? For example, should they be lexicographically sorted or sorted by the time they represent?
Should I validate that the resulting hour is less than 12 and the resulting minute is less than 60 before adding it to the result?

Brute Force Solution

Approach

We're trying to find all possible times that can be represented on a binary watch, given a certain number of lights are on. The brute force method explores every single combination of lights to see if it represents a valid time. We simply check all possibilities.

Here's how the algorithm would work step-by-step:

Consider all possible combinations of turning on zero lights, then one light, then two lights, and so on, until we reach the given number of lights that should be on.
For each combination of lights that are on, determine the corresponding hour and minute values.
Check if the hour and minute are valid (hour must be between 0 and 11, minute between 0 and 59).
If the hour and minute are valid, record that time as a possible solution.
After checking all possible combinations of lights, return the list of all valid times that were found.

Code Implementation

def binary_watch(turned_on_lights):
    possible_times = []

    for hour in range(12):
        for minute in range(60):
            # Count set bits to find valid times.
            if (bin(hour).count('1') + bin(minute).count('1')) == turned_on_lights:
                possible_times.append("%d:%02d" % (hour, minute))

    return possible_times

Big(O) Analysis

Time Complexity

O(1) – The number of lights on the watch is fixed at 10 (4 for hours and 6 for minutes). We iterate through all possible combinations of these 10 lights. The number of iterations is determined by the number of turned-on lights 'n', which is the input. However, since 'n' is constrained to be between 0 and 10, the maximum number of combinations we explore is limited by the binomial coefficient (10 choose n), which is a constant value for any given n within the valid range. Therefore, the runtime does not scale with a variable input size; the number of operations is bounded by a constant, making the time complexity O(1).

Space Complexity

O(1) – The algorithm primarily uses a constant amount of space. It involves checking combinations of lights and recording valid times. While a list of valid times is created as the output, this is not considered auxiliary space. The space used for storing the hour and minute values during validation, along with a few other temporary variables, remains constant regardless of the number of lights (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The binary watch puzzle involves figuring out how many combinations of lights on the watch add up to a specific number. The fastest approach is to realize we can systematically check all possible combinations of bits allocated to hours and minutes, rather than generating and filtering.

Here's how the algorithm would work step-by-step:

Consider that the watch has two sets of lights: some representing the hours and some representing the minutes.
Recognize that each light is either on or off, similar to a binary bit being either 1 or 0.
Systematically go through all possible ways to split the lights between the hours and minutes.
For each split, calculate the hour value and the minute value represented by the lit lights.
Check if the calculated hour is valid (0 to 11) and the minute is valid (0 to 59).
If both hour and minute are valid, and the total number of lights turned on equals the given number, record the combination.
Repeat this process for all possible splits of lights between hours and minutes.
This way, you explore all valid combinations in an organized fashion, avoiding unnecessary calculations or redundant checks.

Code Implementation

def read_binary_watch(turned_on): 
    time_combinations = []

    # Iterate through all possible hour values
    for hour_value in range(12): 

        # Iterate through all possible minute values
        for minute_value in range(60): 

            # Count the total number of set bits (1s)
            total_bits_set = bin(hour_value).count('1') + bin(minute_value).count('1')

            # Check if the total matches the target
            if total_bits_set == turned_on:

                # Format the valid time as 'H:MM'
                time_combinations.append("%d:%02d" % (hour_value, minute_value))

    return time_combinations

def main():
    number_of_lights_on = 1
    possible_times = read_binary_watch(number_of_lights_on)
    print(f"Possible times with {number_of_lights_on} lights on: {possible_times}")

    number_of_lights_on = 2
    possible_times = read_binary_watch(number_of_lights_on)
    print(f"Possible times with {number_of_lights_on} lights on: {possible_times}")

    # Edge case: all lights off
    number_of_lights_on = 0
    possible_times = read_binary_watch(number_of_lights_on)
    print(f"Possible times with {number_of_lights_on} lights on: {possible_times}")

    # Edge case: all lights on, this will return empty array as its not possible within the
    # constrains
    number_of_lights_on = 10
    possible_times = read_binary_watch(number_of_lights_on)
    print(f"Possible times with {number_of_lights_on} lights on: {possible_times}")

if __name__ == "__main__":
    main()

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates through all possible combinations of hours and minutes, which is a fixed number of iterations. The maximum number of possible lit lights on the watch is 10, and we are iterating through every combination of those lights regardless of the input 'n'. The number of operations does not scale with the input 'n', making the time complexity constant.

Space Complexity

O(1) – The provided solution primarily uses integer variables to store the current hour, minute, and the number of lit lights. The algorithm iterates through combinations, calculating hours and minutes, but it doesn't store a collection of intermediate or final results that would scale with the input. Therefore, the extra space used is constant and independent of the number of turned on lights (n), making the space complexity O(1).

Edge Cases

Case	How to Handle
Input number of turned on LEDs 'n' is negative	Return an empty list or throw an IllegalArgumentException as the number of LEDs cannot be negative.
Input number of turned on LEDs 'n' is greater than 10	Return an empty list or throw an IllegalArgumentException as the maximum number of LEDs is 10.
n = 0 (no LEDs turned on)	This should return '0:00' as the only valid time.
n = 10 (all LEDs turned on)	This will result in the time '19:15' and needs to be properly calculated and formatted.
Combinations that result in invalid hours (hour > 11)	Skip combinations that result in hours greater than 11 during the time calculation.
Combinations that result in invalid minutes (minutes > 59)	Skip combinations that result in minutes greater than 59 during the time calculation.
Combinations that result in valid times but hour or minutes are single digit.	Pad the minutes with a leading zero if it is less than 10 to maintain the 'X:XX' format.
Multiple combinations result in the same time.	Since we calculate based on the number of LEDs, avoid duplicates, typically the generation inherently handles this, but should be checked.

Input number of turned on LEDs 'n' is negative

How to Handle:

Return an empty list or throw an IllegalArgumentException as the number of LEDs cannot be negative.

Input number of turned on LEDs 'n' is greater than 10

How to Handle:

Return an empty list or throw an IllegalArgumentException as the maximum number of LEDs is 10.

n = 0 (no LEDs turned on)

How to Handle:

This should return '0:00' as the only valid time.

n = 10 (all LEDs turned on)

How to Handle:

This will result in the time '19:15' and needs to be properly calculated and formatted.

Combinations that result in invalid hours (hour > 11)

How to Handle:

Skip combinations that result in hours greater than 11 during the time calculation.

Combinations that result in invalid minutes (minutes > 59)

How to Handle:

Skip combinations that result in minutes greater than 59 during the time calculation.

Combinations that result in valid times but hour or minutes are single digit.

How to Handle:

Pad the minutes with a leading zero if it is less than 10 to maintain the 'X:XX' format.

Multiple combinations result in the same time.

How to Handle:

Since we calculate based on the number of LEDs, avoid duplicates, typically the generation inherently handles this, but should be checked.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The problem states we need to represent hours and minutes. Can you clarify the valid range for the input 'turnedOn' (number of lit LEDs)? For example, can it be negative, zero, or greater than the maximum number of LEDs (10)?
What should the function return if the given 'turnedOn' value cannot represent any valid time (e.g., too many LEDs to represent a valid hour and minute)? Should I return an empty list, null, or throw an exception?
Are the hours represented in 12-hour format (1-12) or 24-hour format (0-23)? Minutes should be between 0-59, correct?
Is there any specific order required for the output strings in the list? For example, should they be lexicographically sorted or sorted by the time they represent?
Should I validate that the resulting hour is less than 12 and the resulting minute is less than 60 before adding it to the result?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider all possible combinations of turning on zero lights, then one light, then two lights, and so on, until we reach the given number of lights that should be on.
For each combination of lights that are on, determine the corresponding hour and minute values.
Check if the hour and minute are valid (hour must be between 0 and 11, minute between 0 and 59).
If the hour and minute are valid, record that time as a possible solution.
After checking all possible combinations of lights, return the list of all valid times that were found.

Code Implementation

def binary_watch(turned_on_lights):
    possible_times = []

    for hour in range(12):
        for minute in range(60):
            # Count set bits to find valid times.
            if (bin(hour).count('1') + bin(minute).count('1')) == turned_on_lights:
                possible_times.append("%d:%02d" % (hour, minute))

    return possible_times

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Consider that the watch has two sets of lights: some representing the hours and some representing the minutes.
Recognize that each light is either on or off, similar to a binary bit being either 1 or 0.
Systematically go through all possible ways to split the lights between the hours and minutes.
For each split, calculate the hour value and the minute value represented by the lit lights.
Check if the calculated hour is valid (0 to 11) and the minute is valid (0 to 59).
If both hour and minute are valid, and the total number of lights turned on equals the given number, record the combination.
Repeat this process for all possible splits of lights between hours and minutes.
This way, you explore all valid combinations in an organized fashion, avoiding unnecessary calculations or redundant checks.

Code Implementation

def read_binary_watch(turned_on): 
    time_combinations = []

    # Iterate through all possible hour values
    for hour_value in range(12): 

        # Iterate through all possible minute values
        for minute_value in range(60): 

            # Count the total number of set bits (1s)
            total_bits_set = bin(hour_value).count('1') + bin(minute_value).count('1')

            # Check if the total matches the target
            if total_bits_set == turned_on:

                # Format the valid time as 'H:MM'
                time_combinations.append("%d:%02d" % (hour_value, minute_value))

    return time_combinations

def main():
    number_of_lights_on = 1
    possible_times = read_binary_watch(number_of_lights_on)
    print(f"Possible times with {number_of_lights_on} lights on: {possible_times}")

    number_of_lights_on = 2
    possible_times = read_binary_watch(number_of_lights_on)
    print(f"Possible times with {number_of_lights_on} lights on: {possible_times}")

    # Edge case: all lights off
    number_of_lights_on = 0
    possible_times = read_binary_watch(number_of_lights_on)
    print(f"Possible times with {number_of_lights_on} lights on: {possible_times}")

    # Edge case: all lights on, this will return empty array as its not possible within the
    # constrains
    number_of_lights_on = 10
    possible_times = read_binary_watch(number_of_lights_on)
    print(f"Possible times with {number_of_lights_on} lights on: {possible_times}")

if __name__ == "__main__":
    main()

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input number of turned on LEDs 'n' is negative	Return an empty list or throw an IllegalArgumentException as the number of LEDs cannot be negative.
Input number of turned on LEDs 'n' is greater than 10	Return an empty list or throw an IllegalArgumentException as the maximum number of LEDs is 10.
n = 0 (no LEDs turned on)	This should return '0:00' as the only valid time.
n = 10 (all LEDs turned on)	This will result in the time '19:15' and needs to be properly calculated and formatted.
Combinations that result in invalid hours (hour > 11)	Skip combinations that result in hours greater than 11 during the time calculation.
Combinations that result in invalid minutes (minutes > 59)	Skip combinations that result in minutes greater than 59 during the time calculation.
Combinations that result in valid times but hour or minutes are single digit.	Pad the minutes with a leading zero if it is less than 10 to maintain the 'X:XX' format.
Multiple combinations result in the same time.	Since we calculate based on the number of LEDs, avoid duplicates, typically the generation inherently handles this, but should be checked.

Input number of turned on LEDs 'n' is negative

How to Handle:

Return an empty list or throw an IllegalArgumentException as the number of LEDs cannot be negative.

Input number of turned on LEDs 'n' is greater than 10

How to Handle:

Return an empty list or throw an IllegalArgumentException as the maximum number of LEDs is 10.

n = 0 (no LEDs turned on)

How to Handle:

This should return '0:00' as the only valid time.

n = 10 (all LEDs turned on)

How to Handle:

This will result in the time '19:15' and needs to be properly calculated and formatted.

Combinations that result in invalid hours (hour > 11)

How to Handle:

Skip combinations that result in hours greater than 11 during the time calculation.

Combinations that result in invalid minutes (minutes > 59)

How to Handle:

Skip combinations that result in minutes greater than 59 during the time calculation.

Combinations that result in valid times but hour or minutes are single digit.

How to Handle:

Pad the minutes with a leading zero if it is less than 10 to maintain the 'X:XX' format.

Multiple combinations result in the same time.

How to Handle:

Since we calculate based on the number of LEDs, avoid duplicates, typically the generation inherently handles this, but should be checked.