• Posts

Problem 3185 Count Pairs That Form a Complete Day II

Problem Statement

Link - Problem 3185

Question

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.

Example 1:

Example 2:

Constraints:

• 1 <= hours.length <= 5 * 105
• 1 <= hours[i] <= 109

Solution

class Solution {
public:
    long long countCompleteDayPairs(vector<int>& hours) {
        unordered_map<int, int> seenMap;
        long long count = 0;

        for (int hour : hours) {
            int rem = hour % 24;
            int complement = (24 - rem) % 24;
            if (seenMap.find(complement) != seenMap.end()) {
                count += seenMap[complement];
            }
            seenMap[rem]++;
        }

        return count;
    }
};

Complexity Analysis

| Algorithm                   | Time Complexity | Space Complexity |
| --------------------------- | --------------- | ---------------- |
| Hash Table Complement Count | O(n)            | O(1)             |

Explanation

Intial Thoughts

To solve this problem, we need to identify pairs of hours that sum up to a complete day, which is a multiple of 24 hours. We can start by examining each hour in the array and checking if its complement, or the number of hours needed to complete a day, exists in the array. We can use the modulo operator to find the remainder of each hour when divided by 24. This will help us find the complements more efficiently. We can also use a data structure like a hashmap to store the hours we have seen so far and their frequencies. This will allow us to quickly look up the complements and count the pairs. Initially, we should focus on understanding the properties of complete days and how to calculate the complements of each hour.

Intuitive Analysis

Intuitively, we can think of this problem as finding pairs of puzzle pieces that fit together to form a complete picture, which is a complete day in this case. We can start by grouping the hours into categories based on their remainders when divided by 24. This will help us identify the potential complements and find the pairs more efficiently. We can also use the fact that if a pair of hours sums up to a complete day, then their complements will also sum up to a complete day. This symmetry can help us reduce the number of cases we need to consider and make the solution more efficient. Additionally, we should consider using a data structure that allows us to quickly look up the complements and count the pairs, such as a hashmap. By combining these insights, we can develop a solution that is both efficient and easy to understand.

1. Intuition

• The problem requires finding pairs of indices in the hours array where the sum of the hours at these indices forms a complete day, which is a multiple of 24 hours.
• To approach this problem, we need to think about how to efficiently find pairs that sum up to a multiple of 24, considering the large range of possible hour values.
• A key insight is to use the modulo operation to reduce the problem space, focusing on the remainder of each hour when divided by 24.
• This insight allows us to categorize hours based on their remainder when divided by 24, facilitating the identification of complementary pairs.
• The solution works by maintaining a count of seen remainders and their complements, enabling the efficient calculation of pairs that form a complete day.
• The use of an unordered map to store seen remainders and their counts provides an efficient way to look up complements and update counts.
• This approach ensures that each pair is counted exactly once, avoiding double counting and ensuring accuracy.

2. Implementation

• The solution utilizes an unordered_map called seenMap to store the count of each remainder when an hour is divided by 24, with seenMap[rem] representing the count of hours with remainder rem.
• For each hour in the hours array, the remainder rem is calculated as hour % 24, and its complement is determined as (24 - rem) % 24 to handle cases where rem is 0.
• The code checks if the complement of the current remainder is already in seenMap, and if so, increments the count of complete day pairs by the count of the complement, using count += seenMap[complement].
• After updating the count, the code increments the count of the current remainder in seenMap using seenMap[rem]++, preparing for the next iteration.
• The final count of complete day pairs is returned as a long long value, ensuring sufficient range to accommodate large inputs.
• The use of unordered_map allows for efficient lookups and updates, with an average time complexity of O(1), making the overall solution efficient for large inputs.

Complexity Analysis

Time Complexity:

• The algorithm iterates through the hours vector once, resulting in a linear time complexity. Each iteration involves constant-time operations such as calculating rem and complement, and looking up elements in the seenMap.
• The dominant operation is the iteration itself, which is directly proportional to the size of the input vector hours. The seenMap operations, including find and ++, have an average time complexity of O(1) due to the hash table implementation.
• Therefore, the overall time complexity is O(n), where n is the number of elements in the hours vector, since the number of operations grows linearly with the size of the input.

Space Complexity:

• The algorithm uses an unordered_map called seenMap to store the frequency of each hour. In the worst case, every hour could be unique, resulting in seenMap containing n elements.
• The size of seenMap is directly proportional to the number of unique hours in the input vector hours. However, since there are only 24 possible unique hours (0-23), the space complexity is actually bounded by a constant, regardless of the input size.
• Hence, the space complexity is O(1), since the memory usage does not grow with the size of the input vector hours, but is instead limited by the fixed number of possible unique hours.

Footnote

This question is rated as Medium difficulty.

Hints

A pair (i, j) forms a valid complete day if (hours[i] + hours[j]) % 24 == 0.

Using an array or a map, for each index j moving from left to right, increase the answer by the count of (24 - hours[j]) % 24, and then increase the count of hours[j].

Similar Questions: