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. For each hour value x in the array, we need to find how many previously seen values can pair with x to form a multiple of 24.

The key insight is that two numbers sum to a multiple of 24 if and only if their remainders when divided by 24 sum to either 0 or 24. So for a value x, we need to find values that have a remainder of (24 - (x % 24)) % 24 when divided by 24.

The algorithm maintains a counter cnt that tracks how many times each remainder (0 through 23) has appeared so far. For each new hour value x:

1. We calculate what remainder would complement x to form a multiple of 24: (24 - (x % 24)) % 24
2. We add the count of previously seen values with this complementary remainder to our answer
3. We increment the count for x % 24 in our counter for future pairs

This approach ensures we only count valid pairs where i < j since we only look at previously processed elements when finding pairs for the current element.

Intuition

When we need to find pairs that sum to a multiple of 24, we can think about this problem in terms of remainders. If two numbers add up to a multiple of 24, what can we say about their remainders when divided by 24?

Let's consider two numbers a and b. If a + b is divisible by 24, then (a % 24) + (b % 24) must equal either 0 or 24. This is because:

• If both remainders are 0, their sum is 0
• If the remainders sum to 24, they "complete" another full cycle of 24
• Any sum greater than 24 would mean we have another full cycle plus some remainder

So for any hour value x with remainder r = x % 24, we need to find values with remainder 24 - r to form a complete day. But there's a special case: when r = 0, we need another value with remainder 0 (not 24). This is why we use the formula (24 - (x % 24)) % 24 - the outer modulo handles the case when x % 24 = 0.

The natural approach would be to check every pair, but that would be O(n²). Instead, we can be smarter: as we traverse the array, we keep track of how many times we've seen each possible remainder (0 through 23). When we encounter a new value, we immediately know how many previous values it can pair with by looking up the count of its complementary remainder.

This transforms our problem from "find all pairs" to "for each element, count how many previous elements can pair with it" - a classic pattern that reduces time complexity from O(n²) to O(n) by trading space for time with a frequency counter.

Solution Approach

The implementation uses a counting approach with a hash table (Counter in Python) to efficiently track remainders and find valid pairs.

Data Structure:

• cnt: A Counter (hash table) that stores the frequency of each remainder value (0 through 23)
• ans: An accumulator for the total number of valid pairs

Algorithm Steps:

1. Initialize the counter and answer

   • Create an empty Counter cnt to track remainder frequencies
   • Set ans = 0 to accumulate the pair count

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

   a. Find complementary pairs

   • Calculate the complementary remainder: (24 - (x % 24)) % 24
   • This gives us the remainder that, when added to x % 24, results in a multiple of 24
   • Add cnt[(24 - (x % 24)) % 24] to our answer - this counts all previous values that can pair with x

   b. Update the counter

   • Increment cnt[x % 24] by 1
   • This records the current value's remainder for future pairs

3. Return the result

   • After processing all elements, ans contains the total number of valid pairs

Why this works:

• By processing elements left to right and only looking at previous counts, we automatically ensure i < j for all pairs
• The formula (24 - (x % 24)) % 24 correctly handles all cases:
  • If x % 24 = 10, we need remainder 14 (since 10 + 14 = 24)
  • If x % 24 = 0, we need remainder 0 (since 0 + 0 = 0, which is divisible by 24)
• Time complexity: O(n) - single pass through the array
• Space complexity: O(1) - at most 24 different remainder values to store

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 values with remainder 12)
• Add to 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 (found one previous 12!)
• Add to answer: ans = 0 + 1 = 1 (pair found: indices 0,1)
• 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 values with remainder 18)
• Add to 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 values with remainder 0)
• Add to 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 (found one previous 24!)
• Add to answer: ans = 1 + 1 = 2 (pair found: indices 3,4)
• Update counter: cnt[0] = 2
• Final state: cnt = {12: 2, 6: 1, 0: 2}, ans = 2

Result: 2 pairs form complete days:

• Pair (0,1): 12 + 12 = 24 ✓
• Pair (3,4): 24 + 24 = 48 ✓

The algorithm correctly identifies both pairs by tracking remainders and finding complements.

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: computing 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 different keys (representing hours modulo 24, from 0 to 23). Since there are only 24 possible remainders when dividing by 24, the space used by the counter is bounded by this constant, regardless of the input size n.

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 - (hour % 24) without the outer modulo operation. This fails for the case when hour % 24 = 0.

Why it's wrong:

• When hour % 24 = 0, we need to pair with another value that has remainder 0
• But 24 - 0 = 24, which is not a valid remainder (remainders range from 0 to 23)
• This would cause us to look for remainder_count[24], which doesn't exist and returns 0, missing valid pairs

Example of incorrect code:

# WRONG - Missing outer modulo
needed_remainder = 24 - (hour % 24)  # When hour % 24 = 0, this gives 24!
total_pairs += remainder_count[needed_remainder]  # Looks for key 24, which doesn't exist

The Solution: Always use (24 - (hour % 24)) % 24 to ensure the result is in the valid range [0, 23]:

# CORRECT - Outer modulo ensures valid remainder
needed_remainder = (24 - (hour % 24)) % 24
# When hour % 24 = 0: (24 - 0) % 24 = 0 ✓
# When hour % 24 = 10: (24 - 10) % 24 = 14 ✓

2. Counting Pairs in Wrong Order

The Pitfall: Updating the counter before checking for pairs, which would incorrectly allow an element to pair with itself.

Example of incorrect code:

# WRONG - Updates counter before checking pairs
for hour in hours:
    remainder_count[hour % 24] += 1  # Updated first
    needed_remainder = (24 - (hour % 24)) % 24
    total_pairs += remainder_count[needed_remainder]  # Now might count self-pairs

Why it's wrong: If an hour value like 12 appears (12 % 24 = 12, needs remainder 12 to form 24), updating the counter first would allow it to pair with itself, violating the i < j constraint.

The Solution: Always check for pairs with previously seen elements before updating the counter:

# CORRECT - Check pairs first, then update
for hour in hours:
    needed_remainder = (24 - (hour % 24)) % 24
    total_pairs += remainder_count[needed_remainder]  # Check previous elements
    remainder_count[hour % 24] += 1  # Then update for future pairs