LeetCode 3185 - Count Pairs That Form a Complete Day II

The problem asks us to count pairs of elements in an integer array hours such that the sum of the two elements is a multiple of 24, which we call a "complete day." Each pair (i, j) must satisfy i < j.

leetcodemediumarrayhash-tablecounting

LeetCode Problem 3185

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem asks us to count pairs of elements in an integer array hours such that the sum of the two elements is a multiple of 24, which we call a "complete day." Each pair (i, j) must satisfy i < j. The input is an array of integers, where each integer represents a duration in hours. The output is a single integer representing the total number of valid pairs.

The constraints indicate that the array can be very large (up to 500,000 elements) and the values can also be very large (up to 1 billion hours). This makes a brute-force solution that checks all pairs infeasible because it would require up to $\frac{n(n-1)}{2}$ operations, which can be over 100 billion operations at maximum input size.

Important edge cases include arrays with repeated values, arrays where all values are multiples of 24, arrays where no pairs sum to a multiple of 24, and very large values that could potentially cause overflow if not handled properly.

Approaches

The brute-force approach is straightforward: iterate over every pair (i, j) in the array, compute their sum, and check if it is divisible by 24. This method is correct because it explicitly checks all possible pairs, but it is too slow for large inputs because its time complexity is $O(n^2)$.

The optimal approach relies on a key observation from modular arithmetic: if hours[i] + hours[j] is divisible by 24, then (hours[i] % 24 + hours[j] % 24) % 24 == 0. This means we only need to track the remainders modulo 24 of all elements. For each element, we check how many previously seen elements have a remainder that complements it to 24. We can efficiently track counts of each remainder using a hash map or fixed-size array of length 24, resulting in a linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Check all pairs explicitly, too slow for large n
Optimal O(n) O(24) = O(1) Use modulo 24 remainders and a frequency array to count valid pairs

Algorithm Walkthrough

  1. Initialize an array count of size 24 to zero. Each index r will store how many elements with remainder r modulo 24 we have seen so far.
  2. Initialize a variable total_pairs to zero. This will accumulate the count of valid pairs.
  3. Iterate through each element h in hours. Compute its remainder rem = h % 24.
  4. Determine the complementary remainder needed to form a multiple of 24: complement = (24 - rem) % 24.
  5. Add the count of elements seen so far with the complementary remainder to total_pairs.
  6. Increment count[rem] by 1 to record that we have now seen another element with remainder rem.
  7. After processing all elements, return total_pairs.

Why it works: The key invariant is that at each step, count[r] stores the number of previously seen elements with remainder r. By adding count[complement] for each new element, we count all valid pairs (i, j) with i < j exactly once. Using modulo 24 ensures we only track relevant information and avoid large sum calculations.

Python Solution

from typing import List

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        count = [0] * 24
        total_pairs = 0
        
        for h in hours:
            rem = h % 24
            complement = (24 - rem) % 24
            total_pairs += count[complement]
            count[rem] += 1
        
        return total_pairs

In this implementation, we initialize a fixed-size list count to store how many elements have each remainder modulo 24. For each element, we calculate the complement that, together with the current remainder, would sum to a multiple of 24. We add the count of previously seen elements with this complement to total_pairs and then increment the count of the current remainder. This guarantees that all valid pairs (i, j) with i < j are counted exactly once.

Go Solution

func countCompleteDayPairs(hours []int) int64 {
    var count [24]int64
    var totalPairs int64 = 0
    
    for _, h := range hours {
        rem := h % 24
        complement := (24 - rem) % 24
        totalPairs += count[complement]
        count[rem]++
    }
    
    return totalPairs
}

The Go version uses a fixed-size array of 24 int64 values to store the remainder counts. We use int64 to prevent overflow for large counts since the number of pairs can be very large. The loop logic mirrors the Python solution exactly, using modulo arithmetic to track and sum the number of valid pairs.

Worked Examples

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

Step h rem complement count before total_pairs
1 12 12 12 [0,...,0] 0
2 12 12 12 [0,...,1,...,0] 1
3 30 6 18 ... 1
4 24 0 0 ... 1
5 24 0 0 ... 2

Output: 2

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

Step h rem complement count before total_pairs
1 72 0 0 [0,...,0] 0
2 48 0 0 ... 1
3 24 0 0 ... 3
4 3 3 21 ... 3

Output: 3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Iterate through the array once, performing constant-time operations per element
Space O(1) Only a fixed-size array of 24 is used, independent of input size

The linear time complexity is efficient enough for arrays up to 500,000 elements. Space usage is minimal because we only need to track 24 remainder counts.

Test Cases

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

# Edge and stress cases
assert Solution().countCompleteDayPairs([24,48,72,96]) == 6     # all multiples of 24
assert Solution().countCompleteDayPairs([1,2,3,4,5]) == 0      # no pair sums to multiple of 24
assert Solution().countCompleteDayPairs([1]*5000) == 0         # large input, all ones
assert Solution().countCompleteDayPairs([12]*10000) == 49995000 # large input, all 12s
Test Why
[12,12,30,24,24] Validates counting with repeated elements and multiple pair sums
[72,48,24,3] Checks multiple valid pairs including zero remainder
[24,48,72,96] All elements are multiples of 24, tests maximum pairing
[1,2,3,4,5] No valid pairs, tests algorithm returns zero correctly
[1]*5000 Large input with no valid pairs, tests performance
[12]*10000 Large input with repeated elements, tests counting of many pairs

Edge Cases

Single Element: If the array has only one element, there are no pairs to form, so the result is 0. The algorithm handles this naturally by iterating over the array and never finding a complement.

All Multiples of 24: If all elements are multiples of 24, every pair sums to a multiple of 24. The algorithm correctly counts these by using remainder 0 and summing count[0] at each step.

Large Values: Since hours[i] can be up to $10^9$, summing two elements could overflow 32-bit integers. Using modulo 24 ensures all operations remain small, and in Go we also use int64 for totalPairs to safely count large numbers of pairs.