Count Pairs That Form a Complete Day I - 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 <= 1001 <= hours[i] <= 109
Approach Overview
Problem Overview: You get an array hours where each value represents time spent on a task. The goal is to count pairs (i, j) such that hours[i] + hours[j] equals a multiple of 24. In other words, the total hours of the pair form a complete day.
Approach 1: Brute Force Pair Checking (O(n2) time, O(1) space)
The most direct approach checks every possible pair of indices. Use two nested loops: the outer loop picks the first element, and the inner loop checks all elements after it. For each pair, compute (hours[i] + hours[j]) % 24. If the result equals 0, the pair forms a complete day and you increment the count. This approach uses constant extra memory because it only tracks the pair count. It works fine for small inputs but becomes inefficient as n grows since it performs roughly n * (n-1) / 2 comparisons.
Approach 2: Remainder Counting with Hash Table (O(n) time, O(1) space)
A faster solution uses modular arithmetic. Instead of comparing raw values, reduce each hour using remainder = hours[i] % 24. Two numbers form a complete day when their remainders add up to 24, or when both are 0. Maintain a frequency map (or fixed array of size 24) storing how many times each remainder has appeared. For every new value, compute its complement (24 - remainder) % 24. If that complement remainder was seen before, those previous elements form valid pairs with the current element. Add that frequency to the answer, then record the current remainder.
This turns pair detection into a constant-time lookup. Each element is processed once, giving O(n) time complexity. The extra memory stays constant because only 24 remainder buckets are stored. The idea is similar to classic problems like Two Sum but applied to modular arithmetic using a hash table or frequency array.
Since the input is just a list of numbers, iteration over the array combined with remainder frequency counting makes the solution both simple and efficient.
Recommended for interviews: Interviewers typically expect the remainder counting approach. Starting with the brute force method shows you understand the pair requirement, but recognizing the % 24 pattern and converting the problem into remainder complements demonstrates stronger algorithmic thinking and reduces the complexity from O(n2) to O(n).
Approach 1: Brute Force Approach
The brute-force approach involves checking every pair of indices i and j (where i < j) in the array. For each pair, we calculate the sum and determine if it's divisible by 24. This approach iterates over each possible pair, making it quite direct but not the most efficient.
This C solution uses two nested loops to iterate through all possible pairs in the array. For each pair, it checks if their sum is divisible by 24, incrementing the count if true.
Complexity
Time Complexity: O(n^2), where n is the length of the array.
Space Complexity: O(1), as no additional space is used except for a few variables.
Approach 2: Optimized Approach Using Remainders
This approach improves efficiency by using a hash map (or simple array) to count the remainders after dividing each hour by 24. We know that two times can form a complete day if their remainders sum to 24 or are both zero. We keep track of how many hours fall into each remainder category and calculate valid pairs based on combinations of these remainders.
In this C solution, we use an array to keep track of the frequency of remainders. We then calculate valid pairs either from remainders that are equal to 0 or complementary such that their sum is 24.
Complexity
Time Complexity: O(n), as we make a single pass through the hours to calculate remainders.
Space Complexity: O(1), since the auxiliary space remains constant.
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), where n is the length of the array. |
| Optimized Approach Using Remainders | Time Complexity: O(n), as we make a single pass through the hours to calculate remainders. |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n²) | O(1) | Good for understanding the problem or when input size is very small. |
| Remainder Counting with Hash Table | O(n) | O(1) | Best general solution. Efficient for large arrays and commonly expected in interviews. |
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 I easy or hard?
Count Pairs That Form a Complete Day I Python/Java solution
How to solve Count Pairs That Form a Complete Day I in O(n)?
What is the best approach for Count Pairs That Form a Complete Day I?
Is Count Pairs That Form a Complete Day I asked at Google/Amazon/Meta?
What data structure is used in Count Pairs That Form a Complete Day I?
What is the time complexity of Count Pairs That Form a Complete Day I?
Ready to solve this problem?
Practice Count Pairs That Form a Complete Day I with our built-in code editor and test cases.
Practice on FleetCode