We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Pairs That Form a Complete Day II

Number: 3418

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer array hours representing times in hours, return the number of pairs i, j where i < j and hours[i] + hours[j] forms a complete day. A complete day is defined as a time duration that is an exact multiple of 24 hours.

Key Insights

  • Reduce each hour to its remainder when divided by 24. The problem then translates to finding pairs whose remainders sum up to 24 (or 0 modulo 24).
  • Use a frequency map (hash table) to count the occurrences for each remainder.
  • For a remainder r, the complement needed is (24 - r) % 24.
  • Special care is needed when r is 0 or when r equals 12 (since 12 is its own complement when 24 is even); in these cases, use the combination formula for counting pairs.
  • Iterate through the remainders and sum the valid pairs while ensuring that each pair is only counted once.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in hours, since we iterate through the list once. Space Complexity: O(1), since the frequency map will have at most 24 entries.

Solution

The solution involves the following steps:

  1. Iterate through the hours array and compute each hour's remainder modulo 24.
  2. Count the frequency of each remainder using a hash table.
  3. For the remainder 0 and for remainder 12 (if present), compute the number of pairs using the combination formula n*(n-1)/2.
  4. For any other remainder r (from 1 to 23), if its complement (24 - r) exists in the frequency map and r is less than its complement to avoid duplicate counts, multiply the counts.
  5. Sum up all the valid pairs to get the final answer.

This approach efficiently counts the pairs by leveraging modular arithmetic and provides the solution in linear time relative to the input size.

Code Solutions

# Python solution for the problem

def count_pairs(hours):
    # Initialize a frequency dictionary for remainders modulo 24
    remainder_counts = {}
    for h in hours:
        r = h % 24
        remainder_counts[r] = remainder_counts.get(r, 0) + 1
    
    pairs = 0
    # Handle the special case for remainder 0 where (0,0) is valid
    if 0 in remainder_counts:
        count = remainder_counts[0]
        pairs += count * (count - 1) // 2
    
    # Process remaining remainders
    # For remainder 12 (because 12 is complementary with itself for modulo 24)
    if 12 in remainder_counts:
        count = remainder_counts[12]
        pairs += count * (count - 1) // 2
    
    # For all other remainders from 1 to 23, ensure that each pair is counted only once
    for r in range(1, 24):
        if r == 12 or r == 0:
            continue
        complement = 24 - r
        # Only count if r < complement to avoid duplication
        if r < complement and complement in remainder_counts:
            pairs += remainder_counts[r] * remainder_counts[complement]
    
    return pairs

# Example usage:
hours = [12, 12, 30, 24, 24]
print(count_pairs(hours))  # Expected output: 2
← Back to All Questions