#3185

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Pairs That Form a Complete Day II

Count the number of valid pairs of hours that form a complete day by checking if their sum is a multiple of 24.

Problem Statement

You are given an array of integers representing times in hours. Your task is to find how many pairs of indices (i, j) such that i < j and the sum of the times at hours[i] + hours[j] forms a complete day. A complete day is defined as any duration that is an exact multiple of 24 hours, such as 24, 48, 72, etc.

For example, in an array hours = [12, 12, 30, 24, 24], the pairs (0, 1) and (3, 4) both sum to 24 and 48 hours, respectively, which forms complete days.

Examples

Example 1

Input: hours = [12,12,30,24,24]

Output: 2

The pairs of indices that form a complete day are (0, 1) and (3, 4) .

Example 2

Input: hours = [72,48,24,3]

Output: 3

The pairs of indices that form a complete day are (0, 1) , (0, 2) , and (1, 2) .

Constraints

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

Solution Approach

Array Scanning with Hash Lookup

Iterate through the array, for each element, check if its complement (to form a complete day) exists in a hash map. If it does, increment the count of valid pairs.

Modulo Operation for Pair Validation

For a pair (i, j) to form a complete day, the sum of hours[i] + hours[j] should be divisible by 24. Use the modulo operation to validate this condition and identify matching pairs.

Efficient Pair Counting

Use a hash map to store the frequency of remainders of each element when divided by 24. This allows for quick lookup and counting of pairs that satisfy the complete day condition.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used for scanning and hash lookup. The best approach runs in O(n) time where n is the length of the array, and uses O(n) space for the hash map storing the frequency of remainders.

What Interviewers Usually Probe

Candidates should demonstrate an understanding of using hash maps for efficient counting.
Look for candidates who leverage the modulo operation correctly to check for complete day pairs.
Pay attention to candidates' ability to reduce complexity using hash lookups rather than brute force approaches.

Common Pitfalls or Variants

Common pitfalls

Failing to handle large input sizes efficiently, especially if using a brute force approach that leads to O(n^2) time complexity.
Incorrectly counting pairs by not properly handling modulo 24 for each element.
Not accounting for cases where the complement exists multiple times in the array, which can lead to over-counting pairs.

Follow-up variants

What if the time array includes values beyond 24 hours?
How would you modify the approach to handle different lengths of arrays, such as very small arrays or arrays with many duplicate values?
Can the solution be optimized further if only one pair is needed rather than all pairs?

FAQ

What is the time complexity of solving the Count Pairs That Form a Complete Day II problem?

The optimal solution has a time complexity of O(n), where n is the length of the array, using array scanning and hash map lookup.

How do you check if two elements form a complete day?

Check if the sum of the two elements is divisible by 24 using the modulo operation. If the result is 0, they form a complete day.

What is the primary pattern for solving this problem?

The problem relies on array scanning plus hash lookup, utilizing a hash map to store remainders and count valid pairs efficiently.

How can GhostInterview help in preparing for problems like this?

GhostInterview helps by guiding users through the problem-solving approach, focusing on hashing techniques and optimizing time complexity.

Can the solution for Count Pairs That Form a Complete Day II be optimized further?

The solution is already optimal with a time complexity of O(n). Further optimizations would likely focus on space complexity or handling edge cases more efficiently.

terminal

Solution

Solution 1: Counting

We can use a hash table or an array $\textit{cnt}$ of length $24$ to record the occurrence count of each hour modulo $24$.

1

2

3

4

5

6

7

8

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

Continue Practicing

#3184 count pairs that form a complete day i #3186 maximum total damage with spell casting #3153 sum of digit differences of all pairs