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 I

Number: 3421

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of integers representing hours, count the number of pairs (i, j) with i < j such that the sum hours[i] + hours[j] is an exact multiple of 24, forming a complete day.

Key Insights

  • Convert each hour to its remainder modulo 24.
  • A valid pair is formed when the sum of two remainders is 0 modulo 24.
  • Group numbers by their remainder to efficiently count complementary pairs.
  • Special handling is needed for remainders 0 and 12, as they pair with themselves.

Space and Time Complexity

Time Complexity: O(n), where n is the number of hours.
Space Complexity: O(1), as the frequency array size is fixed (24).

Solution

We first compute the remainder of each element in the array when divided by 24 and count the frequency using a fixed-size array or hash table. For any remainder r, its complement that sums to a multiple of 24 is (24 - r) % 24. For remainders that pair with themselves (0 and 12), we use the combination formula (n * (n - 1)) / 2 to count valid pairs. For other remainders, we multiply the frequency of r with that of (24 - r) while making sure each complementary pair is only counted once.

Code Solutions

# Python solution for counting pairs that form a complete day
def count_pairs(hours):
    # Create an array to count frequency of remainders modulo 24
    remainder_freq = [0] * 24
    for hour in hours:
        remainder_freq[hour % 24] += 1

    pairs = 0
    # Count pairs for remainder 0 using combination formula
    pairs += (remainder_freq[0] * (remainder_freq[0] - 1)) // 2

    # Count pairs for remainders 1 to 11 by pairing them with their complement (24 - r)
    for r in range(1, 12):
        pairs += remainder_freq[r] * remainder_freq[24 - r]

    # Count pairs for remainder 12 (self-complementary)
    pairs += (remainder_freq[12] * (remainder_freq[12] - 1)) // 2

    return pairs

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