Problem Description

Given an integer array hours representing times in hours, return an integer denoting 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.

For example, 1 day is 24 hours, 2 days is 48 hours, 3 days is 72 hours, and so on.

Intuition

To solve the problem, we focus on finding pairs in the hours array where their sum is divisible by 24. A simple way to determine if a sum is divisible by 24 is to check if the sum modulo 24 equals zero.

To facilitate this, we use a hash table, or array, called cnt to store the count of each remainder when each element of the hours array is divided by 24. This will help us track how many numbers have a specific remainder when divided by 24.

The steps are as follows:

1. Traverse the hours array.
2. For each hour x, calculate how many previous hours would pair with x to complete a day (their total sum is a multiple of 24). The number we are looking for is (24 - (x % 24)) % 24.
3. Use the cnt hash table or array to find how many such numbers have already been counted and add this count to our answer.
4. Finally, update the cnt with the remainder of the current hour modulo 24.

This method is efficient because it allows us to track potential pairs in constant time using the hash table, making it much faster than a nested loop approach.

Solution Approach

To solve the problem efficiently, we employ a counting technique that utilizes a Counter or hash table to keep track of the occurrences of each hour modulo 24. This approach helps us determine the number of valid pairs without considering every possible combination, which would be computationally expensive.

Step-by-Step Explanation

1. Initialize a Counter: We start by initializing a Counter object named cnt. This will be used to count how many times each remainder (obtained by taking modulo 24 of each hour) appears as we iterate through the hours array.

2. Iterate Through the hours Array: We loop over each element x in the hours list. During each iteration, we perform the following actions:

   • Calculate the Complement: Determine the complement remainder required for x to finish a complete day when paired. This is calculated as (24 - (x % 24)) % 24. This expression effectively finds the opposite remainder needed to make the pair sum a multiple of 24.

   • Count Valid Pairs: Use cnt to find how often this complement remainder has appeared before the current hour. These occurrences count the number of valid pairs i, j where i < j.

   • Update the Counter: Increment the count for the current remainder x % 24 in cnt to reflect its occurrence.

3. Return the Result: After iterating through all the hours, the variable ans holds the total number of valid pairs that satisfy the problem's condition.

This counting approach is efficient and ensures that the solution operates in linear time relative to the size of the hours array, i.e., O(n) complexity.

Here's how the code implements the above logic:

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        cnt = Counter()
        ans = 0
        for x in hours:
            ans += cnt[(24 - (x % 24)) % 24]
            cnt[x % 24] += 1
        return ans

Example Walkthrough

Let's illustrate the solution approach using a small example.

Consider the hours array: [8, 16, 8, 16].

Our goal is to find the number of pairs (i, j) such that the sum of hours[i] + hours[j] is an exact multiple of 24, and i < j.

1. Initialize a Counter: We start with an empty Counter called cnt. We'll also initialize a variable ans to store the count of valid pairs.

2. Iterate Through the hours Array:

   • First Hour (x = 8):

     • Calculate the complement: (24 - (8 % 24)) % 24 = 16.
     • cnt[16] is 0 at this point, so no valid pairs are added to ans.
     • Update the Counter: cnt now becomes {8: 1}.

   • Second Hour (x = 16):

     • Calculate the complement: (24 - (16 % 24)) % 24 = 8.
     • cnt[8] is 1, meaning we have seen one 8 before. So, we add 1 to ans making ans = 1.
     • Update the Counter: cnt now becomes {8: 1, 16: 1}.

   • Third Hour (x = 8):

     • Calculate the complement: (24 - (8 % 24)) % 24 = 16.
     • cnt[16] is 1, so we add 1 to ans making ans = 2.
     • Update the Counter: cnt now becomes {8: 2, 16: 1}.

   • Fourth Hour (x = 16):

     • Calculate the complement: (24 - (16 % 24)) % 24 = 8.
     • cnt[8] is 2, meaning we've seen two 8s before. So, we add 2 to ans, making ans = 4.
     • Update the Counter: cnt now becomes {8: 2, 16: 2}.

3. Return the Result: After processing the entire hours array, the total number of valid pairs is 4. This is the result that meets the condition of sum being a multiple of 24.

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        cnt = Counter()
        ans = 0
        for x in hours:
            ans += cnt[(24 - (x % 24)) % 24]
            cnt[x % 24] += 1
        return ans

# Using the walkthrough example:
s = Solution()
print(s.countCompleteDayPairs([8, 16, 8, 16]))  # Output: 4

Solution Implementation

Time and Space Complexity

The code iterates over each element in the hours list once, performing constant-time operations per element, which results in a time complexity of O(n), where n is the length of the array hours.

For space complexity, a Counter is used to store values based on the remainder when each hour is divided by 24. Since there are at most 24 unique remainders (from 0 to 23), the space complexity is O(24), which simplifies to O(1) as it does not depend on the size of the input.

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