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

Number of Valid Clock Times

Number: 2528

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a string representing a time in the format "hh:mm" where some digits may be replaced by the '?' character, the task is to count how many valid clock times (from "00:00" to "23:59") can be formed by replacing every '?' with a digit from 0 to 9.

Key Insights

  • The problem can be separated into two independent parts: the hour ("hh") and minute ("mm") segments.
  • Each '?' in the hour or minute segment has a constrained set of valid replacements.
  • For the hour:
    • When both characters are unknown, the total combinations are 24.
    • When one character is known and the other is '?', the valid replacements depend on the known digit.
  • For the minutes:
    • When both characters are unknown, the total combinations are 60.
    • When one character is unknown, constraints based on "mm" being between "00" and "59" apply.
  • The final answer is the product of the possibilities for the hours and the minutes.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

We solve the problem by computing the number of valid possibilities for the hour and minute segments separately, then multiplying these counts to get the final answer.

For the hour segment ("hh"):

  • If both characters are '?', there are 24 valid combinations.
  • If the first character is '?' but the second is a digit d:
    • If d is between 0 and 3 (inclusive), the first digit can be 0, 1, or 2 (3 possibilities).
    • Otherwise, it can only be 0 or 1 (2 possibilities).
  • If the second character is '?' but the first is a digit:
    • If the first digit is '2', then the second digit can be 0-3 (4 possibilities).
    • Otherwise, it can be any digit from 0 to 9 (10 possibilities).
  • If there is no '?', then the hour is valid only if it is between 00 and 23 (1 possibility).

For the minute segment ("mm"):

  • If both characters are '?', there are 60 valid combinations.
  • If the first character is '?' but the second is a digit, then it can only be 0 through 5 (6 possibilities).
  • If the second character is '?' but the first is a digit, then it can be any digit from 0 to 9 (10 possibilities).
  • If no '?' exists, then the minute is valid (1 possibility).

Multiply the possibilities from the hours and minutes segments to obtain the answer.

Code Solutions

# Python solution for "Number of Valid Clock Times"
def countTime(time: str) -> int:
    # Calculate hour possibilities
    hour = time[0:2]
    if hour[0] == '?' and hour[1] == '?':
        hour_count = 24
    elif hour[0] == '?':
        # Only the first digit is unknown. The second digit is fixed.
        if int(hour[1]) < 4:  # If minute digit less than 4, valid hour tens: 0, 1, 2
            hour_count = 3
        else:
            hour_count = 2  # Only 0 and 1 possible since "2" would make a >= 24 value if hour[1] >=4
    elif hour[1] == '?':
        # Only the second digit is unknown.
        if hour[0] == '2':
            hour_count = 4  # Only digits 0-3 can be used when the hour starts with '2'
        else:
            hour_count = 10  # Otherwise, digit can be any from 0 to 9
    else:
        hour_count = 1  # No missing digit, so only one valid possibility
    
    # Calculate minute possibilities
    minute = time[3:5]
    if minute[0] == '?' and minute[1] == '?':
        minute_count = 60
    elif minute[0] == '?':
        minute_count = 6  # First digit can be 0 to 5
    elif minute[1] == '?':
        minute_count = 10  # Second digit can be 0 to 9
    else:
        minute_count = 1  # No missing digit
    
    # Total number of valid times is the product of possibilities for hours and minutes.
    return hour_count * minute_count

# Example usage:
print(countTime("?5:00"))  # Expected output: 2
print(countTime("0?:0?"))  # Expected output: 100
print(countTime("??:??"))  # Expected output: 1440
← Back to All Questions