3185. Count Pairs That Form a Complete Day II

MediumArrayHash TableCounting

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 efficiently, the key observation is to focus on the relationship between the hours and multiples of 24. The challenge is to find pairs of indices whose corresponding values in hours sum up to a multiple of 24.

The main insight is to consider the remainder when dividing each hour by 24. This operation allows us to group hours into classes with similar properties when considering their sums modulo 24. Now, instead of keeping track of the entire hours array, we only track these remainders.

Using a hash table (cnt) that counts occurrences of each possible remainder (0 through 23) makes it feasible to determine how many previously seen values, when added to the current hour, will sum to a multiple of 24. Specifically, for each hour x, the number needed to complete a day (a multiple of 24) when added to x is given by (24 - (x % 24)) % 24.

By incrementing the count of x % 24 each time we encounter an element, and simultaneously accumulating how many times the needed complement has previously occurred, the solution efficiently counts the desired pairs during a single pass through the array.

Solution Approach

The solution employs a Counting approach using a hash table (or array) to keep track of occurrences of remainders when each element of hours is divided by 24. Here's a step-by-step walkthrough of the approach:

Initialize a Counter: We use a counter cnt to store the frequency of each possible remainder (from 0 to 23). This will help us quickly check how many hours previously encountered would pair with a given hour to form a complete day.
Iterate over Hours: For each hour x in the hours array:
- Calculate the remainder of x modulo 24, i.e., x % 24. This step normalizes the hour value into a category based on its contribution to a complete day.
- Determine the required remainder for x to form a complete day with previously seen hours: (24 - (x % 24)) % 24. This computation identifies how much more is needed to reach the next multiple of 24 hours from the current x.
- Increment the count of pairs: Use the counter cnt to add the frequency of the identified required remainder to the result variable ans, since these are the instances seen so far that can satisfy the condition with the current x.
Update the Counter: After processing each hour x, update the counter cnt by incrementing the frequency of x % 24. This records that this particular remainder has been encountered once more.
Return the Result: At the end of this process, ans holds the total number of valid pairs where the sum of hours equals a complete day, and this value is returned.

This method ensures that the entire computation is done in a single pass through the array, offering an efficient solution with a complexity of O(n), where n is the number of elements in hours.

Here is the solution code encapsulated within a class:

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

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution using a simple example:

Given hours = [5, 19, 18, 6], we need to determine the number of pairs (i, j) where hours[i] + hours[j] is a complete day, meaning it is a multiple of 24.

Initialize a Counter: Start with an empty counter cnt to keep track of the frequency of remainders when hours are divided by 24.
Initialize Result Counter: Set ans to 0. This will store the final count of valid pairs.
Iterate over Hours:
- For x = 5:
  - Compute remainder: 5 % 24 = 5.
  - Determine the required remainder: (24 - 5) % 24 = 19.
  - Update ans: ans += cnt[19]. Initially, cnt[19] is 0, so ans remains 0.
  - Update counter: cnt[5] += 1. Now, cnt is {5: 1}.
- For x = 19:
  - Compute remainder: 19 % 24 = 19.
  - Determine the required remainder: (24 - 19) % 24 = 5.
  - Update ans: ans += cnt[5]. cnt[5] = 1, so ans becomes 1.
  - Update counter: cnt[19] += 1. Now, cnt is {5: 1, 19: 1}.
- For x = 18:
  - Compute remainder: 18 % 24 = 18.
  - Determine the required remainder: (24 - 18) % 24 = 6.
  - Update ans: ans += cnt[6]. Initially, cnt[6] is 0, so ans remains 1.
  - Update counter: cnt[18] += 1. Now, cnt is {5: 1, 19: 1, 18: 1}.
- For x = 6:
  - Compute remainder: 6 % 24 = 6.
  - Determine the required remainder: (24 - 6) % 24 = 18.
  - Update ans: ans += cnt[18]. cnt[18] = 1, so ans becomes 2.
  - Update counter: cnt[6] += 1. Now, cnt is {5: 1, 19: 1, 18: 1, 6: 1}.
Return the Result: At the end of processing, ans is 2, which means there are two pairs of hours forming complete days: (5, 19) and (18, 6).

This example illustrates the process of calculating remainders, finding complements, updating the count, and how efficiently the pairs are found in one pass through the array.

Solution Implementation

1from typing import List
2from collections import Counter
3
4class Solution:
5    def countCompleteDayPairs(self, hours: List[int]) -> int:
6        counter = Counter()  # To store the frequency of each hour modulo 24
7        total_pairs = 0  # To store the count of complete day pairs
8      
9        for hour in hours:
10            # Compute the remainder modulo 24
11            modulo_value = hour % 24
12            # Find the required complement to complete a full day
13            complement_reminder = (24 - modulo_value) % 24
14            # Increment the number of pairs by the count of needed complements
15            total_pairs += counter[complement_reminder]
16            # Update the counter with the current modulo value
17            counter[modulo_value] += 1
18      
19        return total_pairs
20

1class Solution {
2    public long countCompleteDayPairs(int[] hours) {
3        // Array to hold the count of each hour modulo 24
4        int[] countPerHourModulo = new int[24];
5        long totalPairs = 0;
6      
7        // Iterate over each hour in the given array
8        for (int hour : hours) {
9            // Calculate the complementary hour needed to complete 24 hours (a full day)
10            int complementaryHour = (24 - hour % 24) % 24;
11          
12            // Add the number of complementary hours seen so far to the total answer
13            totalPairs += countPerHourModulo[complementaryHour];
14          
15            // Increment the count of the current hour modulo 24
16            ++countPerHourModulo[hour % 24];
17        }
18        return totalPairs;
19    }
20}
21

1#include <vector>
2
3class Solution {
4public:
5    long long countCompleteDayPairs(std::vector<int>& hours) {
6        int count[24] = {};  // Array to track occurrences of each hour modulo 24.
7        long long completePairs = 0; // Variable to store the number of complete day pairs.
8
9        // Iterate over each hour in the input vector.
10        for (int hour : hours) {
11            // Calculate the complementary hour to form 24 using modulo arithmetic.
12            int complement = (24 - hour % 24) % 24;
13
14            // Add the count of hours that complement the current hour to 24.
15            completePairs += count[complement];
16
17            // Increment the count for the current hour modulo 24.
18            ++count[hour % 24];
19        }
20      
21        // Return the total number of complete day pairs found.
22        return completePairs;
23    }
24};
25

1// Function to count pairs of hours that sum up to 24 (complete days)
2function countCompleteDayPairs(hours: number[]): number {
3    // Initialize an array to keep track of remainders when hours are divided by 24
4    const cnt: number[] = Array(24).fill(0);
5  
6    let ans: number = 0; // Variable to store the count of complete day pairs
7  
8    // Iterate over each hour in the input array
9    for (const hour of hours) {
10        // Calculate the complement remainder to reach 24, then add the number of such occurrences seen before
11        ans += cnt[(24 - (hour % 24)) % 24];
12      
13        // Increment the count of the current hour remainder
14        ++cnt[hour % 24];
15    }
16  
17    return ans; // Return the total number of complete day pairs
18}
19

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array hours. This is because the algorithm iterates through the list hours once, performing constant-time operations for each element.

The space complexity is O(C), where C=24. This is due to the use of a Counter to keep track of distinct modulus results between 0 and 23, which is a constant space independent of the input size n.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: