Number of Valid Clock Times

Problem Statement

Problem Description

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.

Examples

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.

Solution of Given Problem

Intuition and Approach

The problem can be solved using a brute force approach or an optimized Technique.

• Brute Force
• Optimized approach

Approach 1:Brute Force (Naive)

Brute Force Approach:

• Generate all possible combinations by replacing each '?' with digits from 0 to 9.
• Check if the generated time string is valid (i.e., hours should be between 00 and 23, and minutes should be between 00 and 59).
• Count the number of valid times.

Codes in Different Languages

C++

Written by @AmruthaPariprolu

#include <string>
#include <vector>

using namespace std;

bool isValidTime(const string& time) {
    int hours = stoi(time.substr(0, 2));
    int minutes = stoi(time.substr(3, 2));
    return hours >= 0 && hours <= 23 && minutes >= 0 && minutes <= 59;
}

int countValidTimesBruteForce(string time) {
    vector<string> times;
    times.push_back(time);
    for (int i = 0; i < 5; ++i) {
        if (time[i] == '?') {
            int n = times.size();
            for (int j = 0; j < n; ++j) {
                string current = times[j];
                for (int d = 0; d <= 9; ++d) {
                    current[i] = '0' + d;
                    times.push_back(current);
                }
            }
            times.erase(times.begin(), times.begin() + n);
        }
    }
    int validCount = 0;
    for (const auto& t : times) {
        if (isValidTime(t)) {
            ++validCount;
        }
    }
    return validCount;
}

Java

Written by @AmruthaPariprolu

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private boolean isValidTime(String time) {
        int hours = Integer.parseInt(time.substring(0, 2));
        int minutes = Integer.parseInt(time.substring(3, 5));
        return hours >= 0 && hours <= 23 && minutes >= 0 && minutes <= 59;
    }

    public int countValidTimesBruteForce(String time) {
        List<String> times = new ArrayList<>();
        times.add(time);
        for (int i = 0; i < 5; ++i) {
            if (time.charAt(i) == '?') {
                int n = times.size();
                for (int j = 0; j < n; ++j) {
                    String current = times.get(j);
                    for (int d = 0; d <= 9; ++d) {
                        times.add(current.substring(0, i) + d + current.substring(i + 1));
                    }
                }
                times = times.subList(n, times.size());
            }
        }
        int validCount = 0;
        for (String t : times) {
            if (isValidTime(t)) {
                ++validCount;
            }
        }
        return validCount;
    }
}


 

Python

Written by @AmruthaPariprolu

def is_valid_time(time):
    hours = int(time[:2])
    minutes = int(time[3:])
    return 0 <= hours <= 23 and 0 <= minutes <= 59

def count_valid_times_brute_force(time):
    times = [time]
    for i in range(5):
        if time[i] == '?':
            n = len(times)
            for j in range(n):
                current = times[j]
                for d in range(10):
                    times.append(current[:i] + str(d) + current[i+1:])
            times = times[n:]
    valid_count = sum(1 for t in times if is_valid_time(t))
    return valid_count

Complexity Analysis

• Time Complexity: $O(10^k)$
• We generate and check all possible combinations, where k is the number of '?' characters.
• Space Complexity: $O(10^k)$
• We store all possible combinations generated.

Video Explanation of Given Problem

---

Authors:

Loading...