# Number of Valid Clock Times **Difficulty:** EASY [External](https://leetcode.com/problems/number-of-valid-clock-times) Canonical: https://scaleengineer.com/dsa/problems/number-of-valid-clock-times **Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration) **Data structures:** String --- ## Problem You are given a string of length `5` called `time`, representing the current time on a digital clock in the format `"hh:mm"`. The **earliest** possible time is `"00:00"` and the **latest** possible time is `"23:59"`. In the string `time`, the digits represented by the `?` symbol are **unknown**, and must be **replaced** with a digit from `0` to `9`. Return _an integer_ `answer`_, the number of valid clock times that can be created by replacing every_ `?` _with a digit from_ `0` _to_ `9`. **Example 1:** **Input:** time = "?5:00" **Output:** 2 **Explanation:** We can replace the ? with either a 0 or 1, producing "05:00" or "15:00". Note that we cannot replace it with a 2, since the time "25:00" is invalid. In total, we have two choices. **Example 2:** **Input:** time = "0?:0?" **Output:** 100 **Explanation:** Each ? can be replaced by any digit from 0 to 9, so we have 100 total choices. **Example 3:** **Input:** time = "??:??" **Output:** 1440 **Explanation:** There are 24 possible choices for the hours, and 60 possible choices for the minutes. In total, we have 24 * 60 = 1440 choices. **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 `'?'` and need to be replaced with digits from `0` to `9`. # Approaches ## Brute-Force by Iterating All Valid Times This approach involves iterating through every possible valid time from `00:00` to `23:59` and checking if each time matches the given pattern. A counter is incremented for each match. **Time:** O(1), since the number of iterations is constant (24 * 60 = 1440). Each check inside the loop takes constant time. · **Space:** O(1), as it only uses a few variables to store the counter and the formatted time strings. **Pros:** Simple to conceptualize and implement.; Guaranteed to be correct as it exhaustively checks all possibilities. **Cons:** Performs a fixed but relatively large number of operations (1440 checks), which is less efficient than a direct calculation. ### Explanation The core idea is to simulate a digital clock and check every minute of a 24-hour day. We can generate all 1440 possible valid time strings (from `"00:00"` to `"23:59"`) and, for each one, compare it against the input `time` pattern. A helper function can be used to determine if a generated time string matches the pattern. This function compares the two strings character by character. A match occurs at a specific position if the character in the pattern is a `'?'` or if it is identical to the character in the generated time string. If all positions match, the generated time is a valid possibility. For example, if the input is `"?5:00"`, we would iterate from `h=0, m=0` upwards. When we reach `h=5, m=0`, we format it to `"05:00"`. This matches the pattern. When we reach `h=15, m=0`, we format it to `"15:00"`, which also matches. No other time will match, so the final count is 2. ```java class Solution { public int countTime(String time) { int count = 0; // Iterate through all possible hours (0-23) for (int h = 0; h < 24; h++) { // Iterate through all possible minutes (0-59) for (int m = 0; m < 60; m++) { // Format hour and minute to two digits with leading zeros if necessary String hourStr = String.format("%02d", h); String minuteStr = String.format("%02d", m); // Check if the generated time matches the pattern if (matches(time, hourStr, minuteStr)) { count++; } } } return count; } private boolean matches(String pattern, String hour, String minute) { // Check hour part if (pattern.charAt(0) != '?' && pattern.charAt(0) != hour.charAt(0)) { return false; } if (pattern.charAt(1) != '?' && pattern.charAt(1) != hour.charAt(1)) { return false; } // Check minute part if (pattern.charAt(3) != '?' && pattern.charAt(3) != minute.charAt(0)) { return false; } if (pattern.charAt(4) != '?' && pattern.charAt(4) != minute.charAt(1)) { return false; } return true; } } ``` ### Algorithm - Initialize a counter `count` to 0. - Create a nested loop. The outer loop iterates through hours `h` from 0 to 23. - The inner loop iterates through minutes `m` from 0 to 59. - Inside the inner loop, format the current `h` and `m` into two-digit strings `hh` and `mm` (e.g., `5` becomes `"05"`). - Check if the formatted time `hh:mm` matches the input `time` pattern. - A character-by-character comparison is performed. A position matches if the pattern has a `'?'` or if the characters are identical. - If the entire time string matches the pattern, increment `count`. - After the loops complete, return `count`. ## Direct Combinatorial Calculation This is a more efficient approach that calculates the number of possibilities directly using combinatorics. It breaks the problem into two independent parts: counting valid hours and counting valid minutes. The total number of valid times is the product of the results from these two parts. **Time:** O(1), as it involves a fixed number of character lookups, comparisons, and arithmetic operations. · **Space:** O(1), as it only uses a few variables to store the options. **Pros:** Highly efficient, solving the problem with a constant number of simple operations.; Avoids loops and unnecessary computations. **Cons:** The conditional logic, especially for the hour part, is more complex than the brute-force approach and requires careful handling of all cases to avoid errors. ### Explanation Instead of iterating through all 1440 minutes in a day, we can calculate the number of valid choices for the hour and minute components based on the `?` wildcards. The choices for hours and minutes are independent, so we can compute `total_options = hour_options * minute_options`. **Minute Calculation (`mm`):** The minute part `m1m2` is straightforward. `m1` can be `0-5` and `m2` can be `0-9`. - If both `m1` and `m2` are `?`, we have 6 choices for `m1` and 10 for `m2`, giving `6 * 10 = 60` options. - If only `m1` is `?`, we have 6 choices for it (`0-5`). - If only `m2` is `?`, we have 10 choices for it (`0-9`). - If neither is `?`, there is only 1 option. **Hour Calculation (`hh`):** The hour part `h1h2` is more complex because of the `23:59` limit. The choice for `h1` affects the possible choices for `h2` and vice-versa. - If `h1h2` is `"??"`: Any hour from `00` to `23` is possible. Total: 24 options. - If `h1h2` is `"?d"` (e.g., `"?5"`): - If `d >= '4'`, `h1` can be `0` or `1` (e.g., `05`, `15`). 2 options. - If `d <= '3'`, `h1` can be `0`, `1`, or `2` (e.g., `02`, `12`, `22`). 3 options. - If `h1h2` is `"d?"` (e.g., `"1?"`): - If `d` is `0` or `1`, `h2` can be any digit `0-9`. 10 options. - If `d` is `2`, `h2` can be `0-3`. 4 options. - If `h1h2` has no `?`, there is only 1 option. By combining these case analyses, we can find the total possibilities with a few conditional checks. ```java class Solution { public int countTime(String time) { // Calculate possibilities for the hour part int hourOptions; char h1 = time.charAt(0); char h2 = time.charAt(1); if (h1 == '?' && h2 == '?') { hourOptions = 24; } else if (h1 == '?') { if (h2 >= '4') { hourOptions = 2; // h1 can be '0' or '1' } else { hourOptions = 3; // h1 can be '0', '1', or '2' } } else if (h2 == '?') { if (h1 == '2') { hourOptions = 4; // h2 can be '0', '1', '2', '3' } else { // h1 is '0' or '1' hourOptions = 10; // h2 can be '0'-'9' } } else { hourOptions = 1; } // Calculate possibilities for the minute part int minuteOptions; char m1 = time.charAt(3); char m2 = time.charAt(4); if (m1 == '?' && m2 == '?') { minuteOptions = 60; } else if (m1 == '?') { minuteOptions = 6; // m1 can be '0'-'5' } else if (m2 == '?') { minuteOptions = 10; // m2 can be '0'-'9' } else { minuteOptions = 1; } return hourOptions * minuteOptions; } } ``` ### Algorithm - Calculate the number of valid choices for the hour part (`hour_options`). - Let `h1` be `time.charAt(0)` and `h2` be `time.charAt(1)`. - If `h1` and `h2` are both `'?'`, `hour_options` is 24. - If only `h1` is `'?'`, determine `hour_options` (2 or 3) based on the value of `h2`. - If only `h2` is `'?'`, determine `hour_options` (4 or 10) based on the value of `h1`. - If neither is `'?'`, `hour_options` is 1. - Calculate the number of valid choices for the minute part (`minute_options`). - Let `m1` be `time.charAt(3)` and `m2` be `time.charAt(4)`. - If `m1` and `m2` are both `'?'`, `minute_options` is 60. - If only `m1` is `'?'`, `minute_options` is 6. - If only `m2` is `'?'`, `minute_options` is 10. - If neither is `'?'`, `minute_options` is 1. - Return the product `hour_options * minute_options`. # Solutions ### Java ```java class Solution { public int countTime(String time) { int ans = 0; for (int h = 0; h < 24; ++h) { for (int m = 0; m < 60; ++m) { String s = String.format("%02d:%02d", h, m); int ok = 1; for (int i = 0; i < 5; ++i) { if (s.charAt(i) != time.charAt(i) && time.charAt(i) != '?') { ok = 0; break; } } ans += ok; } } return ans; } } ``` ### CPP ```cpp class Solution { public: int countTime(string time) { int ans = 0; for (int h = 0; h < 24; ++h) { for (int m = 0; m < 60; ++m) { char s[20]; sprintf(s, "%02d:%02d", h, m); int ok = 1; for (int i = 0; i < 5; ++i) { if (s[i] != time[i] && time[i] != '?') { ok = 0; break; } } ans += ok; } } return ans; } }; ``` ### Python ```python class Solution: def countTime(self, time: str) -> int: def check(s: str, t: str) -> bool: return all(a == b or b == '?' for a, b in zip(s, t)) return sum(check(f ' { h : 02 d } : { m : 02 d } ', time) for h in range(24) for m in range(60)) ```