Teaching Kids Programming – Number of Valid Clock Times

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Number of Valid Clock Times

The last two digits (seconds) if unknown, we know how many possibilities i.e. the last digit gives 10 valid time, and second last digit (tens second) gives 6.

If the first two are both unknown (the hours), we have 24, from 0 to 23. If the first is unknown, and the second is 0-3, then we have 3 choices 0, 1, and 2. If the second is 4-9, the first digit can only be 0 or 1.

Similarly, if the second digit is unknown, and the first digit is 0 or 1, we have 10 choices for the second digit, otherwise, the second digit could only be 0, 1, 2, and 3 (if the first digit is 2).

Then we have to check each situation (decision making) separately. O(1) constant time and space since we are just doing some counting.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def countTime(self, time: str) -> int:
        ans = 1
        if time[4] == '?':
            ans *= 10
        if time[3] == '?':
            ans *= 6
        if time[0] == '?' and time[1] == '?':
            ans *= 24
        else:
            if time[0] == '?':
                if time[1] <= '3':
                    ans *= 3
                else:
                    ans *= 2
            if time[1] == '?':
                if time[0] <= '1':
                    ans *= 10
                else:
                    ans *= 4
        return ans

class Solution:
    def countTime(self, time: str) -> int:
        ans = 1
        if time[4] == '?':
            ans *= 10
        if time[3] == '?':
            ans *= 6
        if time[0] == '?' and time[1] == '?':
            ans *= 24
        else:
            if time[0] == '?':
                if time[1] <= '3':
                    ans *= 3
                else:
                    ans *= 2
            if time[1] == '?':
                if time[0] <= '1':
                    ans *= 10
                else:
                    ans *= 4
        return ans

This can be also done is a pattern matching via the match keyword supported from Python 3.10.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def countTime(self, t: str) -> int:
        mm = (6 if t[3] == '?' else 1) * (10 if t[4] == '?' else 1)
        match [t[0], t[1]]:
            case ('?', '?'):
                return mm * 24
            case ('?', ('0' | '1' | '2' | '3')):
                return mm * 3
            case ('?', _):
                return mm * 2
            case (('0' | '1'), '?'):
                return mm * 10
            case (_, '?'):
                return mm * 4
        return mm

class Solution:
    def countTime(self, t: str) -> int:
        mm = (6 if t[3] == '?' else 1) * (10 if t[4] == '?' else 1)
        match [t[0], t[1]]:
            case ('?', '?'):
                return mm * 24
            case ('?', ('0' | '1' | '2' | '3')):
                return mm * 3
            case ('?', _):
                return mm * 2
            case (('0' | '1'), '?'):
                return mm * 10
            case (_, '?'):
                return mm * 4
        return mm

We can bruteforce the valid time, hour and mintues, which is 24*60=1440 time, and then count the time that matches the given time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def countTime(self, time: str) -> int:
        ans = 0
        def f(h, m, time):
            s = str(h)
            if h < 10:
                s = "0" + s
            s += ':'
            if m < 10:
                s += "0" + str(m)
            else:
                s += str(m)
            return all(s[i] == time[i] or time[i] == "?" for i in range(5))
 
        for h in range(24):
            for m in range(60):
                if f(h, m, time):
                    ans += 1
        return ans

class Solution:
    def countTime(self, time: str) -> int:
        ans = 0
        def f(h, m, time):
            s = str(h)
            if h < 10:
                s = "0" + s
            s += ':'
            if m < 10:
                s += "0" + str(m)
            else:
                s += str(m)
            return all(s[i] == time[i] or time[i] == "?" for i in range(5))

        for h in range(24):
            for m in range(60):
                if f(h, m, time):
                    ans += 1
        return ans

Time/space complexity is O(1) constant because the problem is bounded.

–EOF (The Ultimate Computing & Technology Blog) —