Number of Valid Clock Times

Easy
1757.

Number of Valid Clock Times

Number of Valid Clock Times is an easy coding problem on strings and enumeration, asked in Amazon and Google interviews.

You are given a string time of length 5 in the form "hh:mm", where some of the digits may have been replaced by '?'. The earliest possible time is "00:00" and the latest is "23:59".

Return the number of valid clock times that can be produced by replacing every '?' with a digit from 0 to 9.

Example 1

Input
time = "?5:00"
Output
2
Explanation
`05:00` and `15:00` are valid; `25:00` is not.

Example 2

Input
time = "0?:0?"
Output
100
Explanation
10 choices for each `?`.

Example 3

Input
time = "??:??"
Output
1440
Explanation
Every minute of the day: 24 × 60.

Constraints

  • time is a valid string of length 5 in the format "hh:mm"
  • "00" <= hh <= "23"
  • "00" <= mm <= "59"
  • some of the digits might be replaced with '?'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} time
 * @return {number}
 */
var countTime = function(time) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Valid Clock Times — Solution in Python, Java & C++

Number of Valid Clock Times solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Number of Valid Clock Times is an easy coding problem on strings and enumeration, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Strings, Enumeration
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string time of length 5 in the form "hh:mm", where some of the digits may have been replaced by '?'. The earliest possible time is "00:00" and the latest is "23:59".

Return the number of valid clock times that can be produced by replacing every '?' with a digit from 0 to 9.

Example 1

Input: time = "?5:00"
Output: 2
Explanation: `05:00` and `15:00` are valid; `25:00` is not.

Example 2

Input: time = "0?:0?"
Output: 100
Explanation: 10 choices for each `?`.

Example 3

Input: time = "??:??"
Output: 1440
Explanation: Every minute of the day: 24 × 60.

Constraints

  • time is a valid string of length 5 in the format "hh:mm"
  • "00" <= hh <= "23"
  • "00" <= mm <= "59"
  • some of the digits might be replaced with '?'

Hints for Number of Valid Clock Times

  1. Hint 1

    The hour and the minutes are independent: the answer is (number of valid hours) × (number of valid minutes).

  2. Hint 2

    Minutes: a ? in the tens place has 6 choices (0–5), a ? in the ones place has 10.

  3. Hint 3

    Hours are the tricky part — the ones digit is limited to 0–3 when the tens digit is 2. Or simply try all 24 hours and see which match the pattern.

How to solve Number of Valid Clock Times

Count matching hours and matching minutes separately and multiply — the two halves of the clock do not constrain each other.

Approach

  1. Count the hours h in 0..23 whose two digits match time[0..1] (a ? matches any digit).
  2. Count the minutes m in 0..59 whose two digits match time[3..4].
  3. Return the product.

Why it works

A time is valid exactly when its hour part is a valid hour and its minute part a valid minute, and the ? positions of the two parts are disjoint, so the choices multiply.

Complexity

  • Time — O(24 + 60)
  • Space — O(1)

Pitfalls

  • "2?" allows only 20–23 (4 choices), while "?4" allows only 04 and 14 (2 choices).
  • "??" for the hour is 24 choices, not 3 × 10.

Reference solution

Python

def countTime(time: str) -> int:
    def matches(value, pattern):
        s = "%02d" % value
        return all(p == "?" or p == c for p, c in zip(pattern, s))

    hours = sum(1 for h in range(24) if matches(h, time[:2]))
    minutes = sum(1 for m in range(60) if matches(m, time[3:]))
    return hours * minutes

Java

static boolean ctFits(int value, char a, char b) {
    return (a == '?' || a - '0' == value / 10) && (b == '?' || b - '0' == value % 10);
}

public static int countTime(String time) {
    int hours = 0, minutes = 0;
    for (int h = 0; h < 24; h++) if (ctFits(h, time.charAt(0), time.charAt(1))) hours++;
    for (int m = 0; m < 60; m++) if (ctFits(m, time.charAt(3), time.charAt(4))) minutes++;
    return hours * minutes;
}

C++

static bool ctFits(int value, char a, char b) {
    return (a == '?' || a - '0' == value / 10) && (b == '?' || b - '0' == value % 10);
}

int countTime(string time) {
    int hours = 0, minutes = 0;
    for (int h = 0; h < 24; h++) if (ctFits(h, time[0], time[1])) hours++;
    for (int m = 0; m < 60; m++) if (ctFits(m, time[3], time[4])) minutes++;
    return hours * minutes;
}

JavaScript

var countTime = function(time) {
    var fits = function(value, a, b) {
        var t = String(Math.floor(value / 10)), o = String(value % 10);
        return (a === "?" || a === t) && (b === "?" || b === o);
    };
    var hours = 0, minutes = 0;
    for (var h = 0; h < 24; h++) if (fits(h, time[0], time[1])) hours++;
    for (var m = 0; m < 60; m++) if (fits(m, time[3], time[4])) minutes++;
    return hours * minutes;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings