Valid Time Combinations

Overview

The objective is to find how many unique, valid 24-hour times (HH:MM) can be constructed using four provided digits. Since we only have four digits, the number of possible arrangements (permutations) is very small.

A 24-hour time is valid if the hours component is between 00 and 23, and the minutes component is between 00 and 59. Because the input digits can be identical, we must ensure that we only count unique time combinations to avoid overcounting.

Brute Force

The brute force approach involves generating every possible permutation of the four input digits. For each permutation, we treat the first two digits as the hour and the last two as the minute. We then validate these against the 24-hour clock rules and store the valid ones in a set to handle uniqueness.

Implementation

import itertools

def count_valid_times(A: int, B: int, C: int, D: int) -> int:
    digits = [A, B, C, D]
    valid_times = set()
    
    # Generate all unique permutations of the 4 digits
    for p in itertools.permutations(digits):
        hour = p[0] * 10 + p[1]
        minute = p[2] * 10 + p[3]
        
        # Validate 24-hour format: HH < 24 and MM < 60
        if 0 <= hour < 24 and 0 <= minute < 60:
            # Store as a tuple or string in a set to ensure uniqueness
            valid_times.add((hour, minute))
            
    return len(valid_times)

Time complexity: O(1) — There are exactly $4! = 24$ permutations to check, which is a constant number of operations regardless of the input values. Space complexity: O(1) — The set stores at most 24 unique time combinations.

Optimal / Best Approach

Since the number of permutations is fixed at 24, the brute force approach is already optimal in terms of complexity. However, we can write a more "manual" version that avoids importing libraries, which is sometimes preferred in low-level environment constraints or specific interview settings.

We can use nested loops to pick digits for each position ($H_1, H_2, M_1, M_2$), ensuring we don't reuse the same digit index.

Implementation

def count_valid_times(A: int, B: int, C: int, D: int) -> int:
    digits = [A, B, C, D]
    unique_combinations = set()
    
    # Try every digit for every position in HH:MM
    for i in range(4): # First hour digit
        for j in range(4): # Second hour digit
            if j == i: continue
            for k in range(4): # First minute digit
                if k == i or k == j: continue
                for l in range(4): # Second minute digit
                    if l == i or l == j or l == k: continue
                    
                    h = digits[i] * 10 + digits[j]
                    m = digits[k] * 10 + digits[l]
                    
                    if h < 24 and m < 60:
                        unique_combinations.add((h, m))
                        
    return len(unique_combinations)

Time complexity: O(1) — Specifically $4 \times 3 \times 2 \times 1 = 24$ iterations. Space complexity: O(1) — Storing at most 24 results in a set.

Why this works

A 24-hour clock has specific constraints on each digit position:

• The first hour digit can only be 0, 1, or 2.
• If the first hour digit is 2, the second must be 0-3.
• The first minute digit can only be 0-5.

By checking every permutation, we implicitly satisfy these constraints when we verify hour < 24 and minute < 60. The use of a Set is the most critical part of the algorithm, as it automatically handles inputs with duplicate digits (like [0, 0, 0, 0]) by ensuring (0, 0) is only counted once.