Count Pairs That Form a Complete Day II - Solution & Explanation
Problem Statement
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] <= 109
Approach Overview
Problem 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 1: Brute Force Approach
This is a straightforward approach where you iterate over all possible pairs in the array and check if their sum is a multiple of 24. Although not optimal, it's the simplest solution to understand the problem and attempt manual calculations for small inputs.
In this C code, we define a function countCompleteDays which processes all possible pairs using nested loops, checking if their sum is divisible by 24 (i.e., (hours[i] + hours[j]) % 24 == 0). The time complexity is O(n^2) since we are checking each pair, and the space complexity is O(1) because we are not using additional storage proportional to the input size.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Optimized Approach Using Hash Map
This approach optimizes the search for pairs whose sums are multiples of 24 by using a hash map (or dictionary) to track previously seen remainders when each hour is divided by 24. This reduces time complexity to linear.
This C code uses an array remainderCount of size 24 to keep track of the frequency of remainders when elements of hours are divided by 24. It efficiently counts pairs forming complete days by using these remainders.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Counting
We can use a hash table or an array cnt of length 24 to record the occurrence count of each hour modulo 24.
Iterate through the array hours. For each hour x, we can find the number that, when added to x, results in a multiple of 24, and after modulo 24, this number is (24 - x bmod 24) bmod 24. We then accumulate the occurrence count of this number from the hash table or array. After that, we increment the occurrence count of x modulo 24 by one.
After iterating through the array hours, we can obtain the number of index pairs that meet the problem requirements.
The time complexity is O(n), where n is the length of the array hours. The space complexity is O(C), where C=24.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Optimized Approach Using Hash Map | Time Complexity: O(n) |
| Counting | — |
Detailed Complexity Analysis
| 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 |
Video Solution
3185. & 3184 Count Pairs That Form a Complete Day II | Same as Two Sum | Modulo Operation • Aryan Mittal • 3,787 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Pairs That Form a Complete Day II easy or hard?
Count Pairs That Form a Complete Day II Python/Java solution
How to solve Count Pairs That Form a Complete Day II in O(n)?
What is the best approach for Count Pairs That Form a Complete Day II?
Is Count Pairs That Form a Complete Day II asked at Google/Amazon/Meta?
What data structure is used in Count Pairs That Form a Complete Day II?
What is the time complexity of Count Pairs That Form a Complete Day II?
Ready to solve this problem?
Practice Count Pairs That Form a Complete Day II with our built-in code editor and test cases.
Practice on FleetCode