Watch 10 video solutions for Count Pairs That Form a Complete Day II, a medium level problem involving Array, Hash Table, Counting. This walkthrough by Aryan Mittal has 3,738 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
Input: hours = [12,12,30,24,24]
Output: 2
Explanation: 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
Explanation: The pairs of indices that form a complete day are (0, 1), (0, 2), and (1, 2).
Constraints:
1 <= hours.length <= 5 * 1051 <= hours[i] <= 109Problem Overview: You are given an array hours where each value represents time spent on a task. Two indices form a valid pair if the total hours add up to a complete day, meaning (hours[i] + hours[j]) % 24 == 0. The goal is to count how many such pairs exist in the array.
Approach 1: Brute Force Pair Checking (O(n²) time, O(1) space)
The simplest method checks every pair of indices using two nested loops. For each i, iterate through j > i and compute (hours[i] + hours[j]) % 24. If the result equals 0, increment the pair count. This approach requires no additional data structures and directly follows the problem definition. However, it performs n(n-1)/2 comparisons, which becomes expensive for large arrays. Use this approach only for small inputs or as a baseline when validating more optimized logic.
Approach 2: Optimized Remainder Counting with Hash Map (O(n) time, O(1) space)
A more efficient approach relies on modular arithmetic. Instead of comparing every pair, compute remainder = hours[i] % 24. For a pair to form a complete day, the second value must contribute (24 - remainder) % 24. Maintain a frequency map that tracks how many times each remainder has appeared so far. For each element, check how many previously seen values match the required complement remainder and add that count to the result.
This works because if two numbers sum to a multiple of 24, their remainders modulo 24 must complement each other. For example, remainder 5 pairs with 19, 8 pairs with 16, and 0 pairs with another 0. The algorithm processes the array once, performing constant-time hash lookups and updates. Since the remainder range is only 0–23, the map size never exceeds 24 entries.
This technique combines ideas from array traversal and frequency counting using a hash table. It is a common pattern in modular pair problems and falls under the broader category of counting techniques used to avoid quadratic comparisons.
Recommended for interviews: Start by explaining the brute force solution to demonstrate understanding of the pairing condition. Then transition to the remainder-counting strategy. Interviewers expect the O(n) hash map approach because it eliminates redundant comparisons and shows comfort with modular arithmetic and frequency maps.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n²) | O(1) | Useful for small inputs or verifying correctness during development |
| Hash Map Remainder Counting | O(n) | O(1) | Best general solution; processes array once using remainder complements |