LeetCode 3184 - Count Pairs That Form a Complete Day I

LeetCode Problem 3184

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem asks us to find all pairs of indices (i, j) in an array hours such that i < j and the sum of hours[i] + hours[j] is an exact multiple of 24, which is considered a "complete day." In simpler terms, we are trying to count all unique pairs of hours that add up to 24, 48, 72, or any multiple of 24.

The input is a list of positive integers, each representing a duration in hours. The output is a single integer representing the total number of valid pairs that form complete days.

The constraints are relatively small: the array has at most 100 elements, and each element can be as large as $10^9$. This tells us that while the array is small, the values are large, so we should avoid approaches that require operations proportional to the value magnitude. The input guarantees positive integers, so we do not need to handle zeros or negative numbers.

Important edge cases include arrays with repeated values that can form multiple pairs, arrays with all elements multiples of 24, and arrays where no pairs form a complete day.

Approaches

The brute-force approach is straightforward: iterate over all possible pairs (i, j) with i < j and check if their sum modulo 24 equals 0. This is guaranteed to give the correct answer because it examines every possible pair, but it requires $O(n^2)$ time, which is acceptable for $n \leq 100$ but inefficient for larger inputs.

A key insight for optimization is to notice that we only care about sums modulo 24. If we calculate the remainder of each number modulo 24, then a pair forms a complete day if the sum of their remainders modulo 24 equals 0. We can use a hash map to count occurrences of each remainder. For each element, we can directly calculate the complementary remainder needed to form a complete day and add the count of elements seen so far with that remainder. This reduces the solution to linear time $O(n)$ and linear space $O(24)$.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks all pairs explicitly
Optimal	O(n)	O(24)	Uses remainder counting with a hash map

Algorithm Walkthrough

1. Initialize a hash map or array remainder_count to keep track of how many numbers have each remainder modulo 24.
2. Initialize a variable pairs to zero to accumulate the count of valid pairs.
3. Iterate through each number in the hours array.
4. For each number, compute remainder = hours[i] % 24.
5. Compute complement = (24 - remainder) % 24. This is the remainder needed from a previous number to form a complete day.
6. Add remainder_count[complement] to pairs because all previously seen numbers with this remainder will form a valid pair with the current number.
7. Increment remainder_count[remainder] to record that we have seen this remainder.
8. After processing all numbers, return pairs.

Why it works: The algorithm works because it exploits the property that two numbers sum to a multiple of 24 if and only if the sum of their remainders modulo 24 is 0. By maintaining counts of remainders seen so far, we can efficiently calculate how many valid pairs each new number contributes without iterating over previous numbers explicitly.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        remainder_count = defaultdict(int)
        pairs = 0
        
        for hour in hours:
            remainder = hour % 24
            complement = (24 - remainder) % 24
            pairs += remainder_count[complement]
            remainder_count[remainder] += 1
        
        return pairs

In this implementation, remainder_count stores how many numbers with each remainder we have seen. For each hour, we calculate the complement needed to complete a day and add the number of previously seen hours with that remainder. Finally, we increment the count for the current remainder for future numbers.

Go Solution

func countCompleteDayPairs(hours []int) int {
    remainderCount := make([]int, 24)
    pairs := 0
    
    for _, hour := range hours {
        remainder := hour % 24
        complement := (24 - remainder) % 24
        pairs += remainderCount[complement]
        remainderCount[remainder]++
    }
    
    return pairs
}

The Go implementation uses an array of size 24 instead of a map because the remainders are guaranteed to be between 0 and 23. Each element contributes to pairs exactly as in Python. We use slice indexing and integer arithmetic, which avoids the overhead of a map.

Worked Examples

Example 1: hours = [12, 12, 30, 24, 24]

Step	hour	remainder	complement	remainder_count	pairs
1	12	12	12	{}	0
2	12	12	12	{12:1}	1
3	30	6	18	{12:2}	1
4	24	0	0	{12:2, 6:1}	1
5	24	0	0	{12:2, 6:1, 0:1}	2

Output: 2

Example 2: hours = [72, 48, 24, 3]

Step	hour	remainder	complement	remainder_count	pairs
1	72	0	0	{}	0
2	48	0	0	{0:1}	1
3	24	0	0	{0:2}	3
4	3	3	21	{0:3}	3

Output: 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the array once and do O(1) operations per element.
Space	O(24) = O(1)	The remainder_count array has fixed size 24, independent of input size.

The time complexity is linear in the number of hours, and the space complexity is effectively constant since the map only needs 24 slots.

Test Cases

# provided examples
assert Solution().countCompleteDayPairs([12,12,30,24,24]) == 2  # two pairs: (0,1), (3,4)
assert Solution().countCompleteDayPairs([72,48,24,3]) == 3      # three pairs: (0,1),(0,2),(1,2)

# edge cases
assert Solution().countCompleteDayPairs([24,24,24,24]) == 6     # all multiples of 24
assert Solution().countCompleteDayPairs([1,2,3,4]) == 0         # no pairs sum to multiple of 24
assert Solution().countCompleteDayPairs([23,1,47,25]) == 3      # various modulo pairs
assert Solution().countCompleteDayPairs([24]) == 0              # only one element
assert Solution().countCompleteDayPairs([24,48,72,96,120]) == 10 # all multiples, all pairs valid

Test	Why
[12,12,30,24,24]	checks normal case with repeated numbers
[72,48,24,3]	checks different multiples of 24
[24,24,24,24]	all numbers multiples of 24, maximum pairs
[1,2,3,4]	no valid pairs, should return 0
[23,1,47,25]	tests complement calculation with remainders
[24]	single element, edge case
[24,48,72,96,120]	all multiples, combinatorial pair count

Edge Cases

One important edge case is when all elements are multiples of 24. In this case, every pair forms a complete day, and the algorithm correctly counts all pairs by tracking remainder 0.

Another edge case is when no two elements can form a complete day. The algorithm handles this gracefully because remainder_count[complement] will always be zero, so pairs remains zero.

A third edge case is arrays containing large numbers, up to $10^9$. Since we only compute the remainder modulo 24, the algorithm does not suffer from integer overflow or performance issues. This ensures that even large inputs are handled efficiently.