Problem Description

You are given an integer array hours where each element represents a time duration in hours. Your task is to find the number of pairs of indices (i, j) where i < j and the sum hours[i] + hours[j] forms a complete day.

A complete day is defined as any time duration that is an exact multiple of 24 hours. For example:

• 24 hours = 1 complete day
• 48 hours = 2 complete days
• 72 hours = 3 complete days
• And so on...

The solution uses a counting approach with modular arithmetic. The key insight is that two numbers form a complete day when their sum is divisible by 24.

For each hour value x in the array, we need to find how many previous values can pair with it to form a multiple of 24. If x % 24 = r, then we need a value y such that (r + y % 24) % 24 = 0. This means y % 24 must equal (24 - r) % 24.

The algorithm maintains a counter cnt that tracks how many times each remainder (when divided by 24) has appeared so far. For each new hour x:

1. Calculate what remainder would complement x to form a complete day: (24 - (x % 24)) % 24
2. Add the count of previous hours with that remainder to the answer
3. Update the counter with x's remainder for future pairs

This approach ensures we only count valid pairs where i < j since we only look at previously seen values when processing each element.

Intuition

The problem asks us to find pairs that sum to multiples of 24. A naive approach would be to check every possible pair, but that would take O(n²) time. We need something more efficient.

Let's think about what makes two numbers add up to a multiple of 24. If we have two numbers a and b, and (a + b) % 24 = 0, then the remainders of a and b when divided by 24 must complement each other to sum to 24 (or 0).

For example:

• If a = 26 (remainder 2), we need b to have remainder 22 so that 2 + 22 = 24
• If a = 48 (remainder 0), we need b to also have remainder 0 so that 0 + 0 = 0
• If a = 13 (remainder 13), we need b to have remainder 11 so that 13 + 11 = 24

This observation leads us to realize that we don't actually care about the full values - we only care about their remainders when divided by 24. Two numbers with the same remainder will behave the same way when looking for pairs.

So the key insight is: for any hour value x with remainder r (where r = x % 24), it can form a complete day with any previous hour value that has remainder (24 - r) % 24. The extra modulo operation handles the edge case where r = 0, ensuring we get 0 instead of 24.

This suggests we can solve the problem in a single pass: as we iterate through the array, we keep track of how many times we've seen each remainder value. For each new element, we check how many previous elements have the complementary remainder, add that to our answer, then update our count for the current element's remainder.

This way, we naturally ensure i < j because we only pair current elements with previously seen ones, and we achieve O(n) time complexity with O(1) extra space (since there are only 24 possible remainders).

Solution Approach

The solution implements the counting approach using a hash table to track remainder frequencies.

Data Structure Used:

• Counter(): A Python dictionary subclass that stores the frequency of each remainder value (0-23)
• ans: An integer to accumulate the total number of valid pairs

Algorithm Steps:

1. Initialize the counter and answer:

   cnt = Counter()
   ans = 0

   The counter starts empty, and we'll build it up as we process each element.

2. Process each hour value: For each x in the hours array:

   a. Find complementary remainder:

   ans += cnt[(24 - (x % 24)) % 24]

   • First, calculate x % 24 to get the remainder of current hour
   • Then find what remainder would complement it: 24 - (x % 24)
   • Apply modulo again to handle the case when x % 24 = 0, which gives us (24 - 0) % 24 = 0
   • Look up how many previous hours had this complementary remainder
   • Add this count to our answer

   b. Update the counter:

   cnt[x % 24] += 1

   • Record that we've seen one more hour with remainder x % 24
   • This will be available for pairing with future elements

3. Return the result: After processing all hours, ans contains the total number of valid pairs.

Why this works:

• By processing elements left to right and only pairing with previously seen elements, we naturally ensure i < j
• The modular arithmetic (24 - (x % 24)) % 24 correctly identifies the complementary remainder for any value
• Using a counter allows O(1) lookups and updates

Time Complexity: O(n) where n is the length of the hours array - we make a single pass through the array Space Complexity: O(1) - the counter can have at most 24 entries regardless of input size

Example Walkthrough

Let's walk through the solution with hours = [12, 12, 30, 24, 24].

Initial State:

• cnt = {} (empty counter)
• ans = 0

Step 1: Process hours[0] = 12

• Calculate remainder: 12 % 24 = 12
• Find complement: (24 - 12) % 24 = 12
• Check counter: cnt[12] = 0 (no previous hours with remainder 12)
• Update answer: ans = 0 + 0 = 0
• Update counter: cnt[12] = 1
• State: cnt = {12: 1}, ans = 0

Step 2: Process hours[1] = 12

• Calculate remainder: 12 % 24 = 12
• Find complement: (24 - 12) % 24 = 12
• Check counter: cnt[12] = 1 (one previous hour with remainder 12)
• Update answer: ans = 0 + 1 = 1 (found pair: indices 0 and 1, since 12 + 12 = 24)
• Update counter: cnt[12] = 2
• State: cnt = {12: 2}, ans = 1

Step 3: Process hours[2] = 30

• Calculate remainder: 30 % 24 = 6
• Find complement: (24 - 6) % 24 = 18
• Check counter: cnt[18] = 0 (no previous hours with remainder 18)
• Update answer: ans = 1 + 0 = 1
• Update counter: cnt[6] = 1
• State: cnt = {12: 2, 6: 1}, ans = 1

Step 4: Process hours[3] = 24

• Calculate remainder: 24 % 24 = 0
• Find complement: (24 - 0) % 24 = 0
• Check counter: cnt[0] = 0 (no previous hours with remainder 0)
• Update answer: ans = 1 + 0 = 1
• Update counter: cnt[0] = 1
• State: cnt = {12: 2, 6: 1, 0: 1}, ans = 1

Step 5: Process hours[4] = 24

• Calculate remainder: 24 % 24 = 0
• Find complement: (24 - 0) % 24 = 0
• Check counter: cnt[0] = 1 (one previous hour with remainder 0)
• Update answer: ans = 1 + 1 = 2 (found pair: indices 3 and 4, since 24 + 24 = 48)
• Update counter: cnt[0] = 2
• State: cnt = {12: 2, 6: 1, 0: 2}, ans = 2

Final Result: 2 pairs

• Pair 1: hours[0] + hours[1] = 12 + 12 = 24 (1 complete day)
• Pair 2: hours[3] + hours[4] = 24 + 24 = 48 (2 complete days)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array hours. This is because the algorithm iterates through the array exactly once, and for each element, it performs constant-time operations: calculating the modulo, looking up a value in the counter, updating the answer, and incrementing the counter.

The space complexity is O(C), where C = 24. The Counter dictionary cnt stores at most 24 distinct keys since we're storing values modulo 24 (i.e., x % 24 can only produce values from 0 to 23). Therefore, regardless of the input size n, the space used by the counter is bounded by the constant 24.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Zero Remainder Case

The Pitfall: A common mistake is writing the complementary remainder calculation as simply 24 - (x % 24) without the outer modulo operation. This fails when x % 24 = 0.

Wrong Implementation:

needed_remainder = 24 - (hour % 24)  # Bug: when hour % 24 = 0, this gives 24 instead of 0

Why it's wrong:

• When hour = 24, we have hour % 24 = 0
• The complement should be 0 (since 0 + 0 = 0, which is divisible by 24)
• But 24 - 0 = 24, which is outside our valid remainder range [0, 23]
• Looking up remainder_count[24] will always return 0, missing valid pairs

Correct Implementation:

needed_remainder = (24 - (hour % 24)) % 24  # Correctly handles all cases

2. Counting Pairs in Wrong Order

The Pitfall: Updating the counter before checking for pairs, which leads to self-pairing when an element could pair with itself.

Wrong Implementation:

for hour in hours:
    remainder_count[hour % 24] += 1  # Updated BEFORE checking
    total_pairs += remainder_count[(24 - (hour % 24)) % 24]

Why it's wrong:

• If we have an hour value like 12, it has remainder 12
• Its complement is also 12 (since 12 + 12 = 24)
• By updating the counter first, we incorrectly count this element as pairing with itself
• This violates the constraint that we need distinct indices i < j

Correct Implementation:

for hour in hours:
    total_pairs += remainder_count[(24 - (hour % 24)) % 24]  # Check FIRST
    remainder_count[hour % 24] += 1  # Update AFTER

3. Using Regular Dictionary Instead of Counter

The Pitfall: Using a regular dictionary and forgetting to handle missing keys.

Wrong Implementation:

remainder_count = {}
for hour in hours:
    needed = (24 - (hour % 24)) % 24
    total_pairs += remainder_count[needed]  # KeyError if 'needed' not in dict

Why it's wrong:

• Regular dictionaries raise KeyError when accessing non-existent keys
• The first element will always cause an error since the dictionary is empty

Correct Implementation:

# Option 1: Use Counter (recommended)
remainder_count = Counter()

# Option 2: Use dict.get() with default value
remainder_count = {}
total_pairs += remainder_count.get(needed, 0)

# Option 3: Check key existence
if needed in remainder_count:
    total_pairs += remainder_count[needed]