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
Hint 1
The hour and the minutes are independent: the answer is (number of valid hours) × (number of valid minutes).
Hint 2
Minutes: a
?in the tens place has 6 choices (0–5), a?in the ones place has 10.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
- Count the hours
hin0..23whose two digits matchtime[0..1](a?matches any digit). - Count the minutes
min0..59whose two digits matchtime[3..4]. - 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 * minutesJava
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