Count Pairs That Form a Complete Day II
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every possible pair of indices (i, j) where i < j. For each pair, we calculate the sum of hours[i] and hours[j] and check if this sum is divisible by 24. If it is, we increment a counter.
Algorithm
- Initialize a counter
countto 0. - Use a nested loop. The outer loop iterates from
i = 0ton-2, wherenis the length of thehoursarray. - The inner loop iterates from
j = i + 1ton-1. - Inside the inner loop, check if
(hours[i] + hours[j]) % 24 == 0. - If the condition is true, increment the
count. - After the loops complete, return
count.
Walkthrough
This method involves a brute-force check of all unique pairs in the array. We use two nested loops to generate these pairs. The outer loop picks the first element of the pair, and the inner loop picks the second element from the rest of the array. For each pair, we perform the check (hours[i] + hours[j]) % 24 == 0. While simple, this approach is computationally expensive.
class Solution { public long countCompleteDayPairs(int[] hours) { long count = 0; int n = hours.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if ((hours[i] + hours[j]) % 24 == 0) { count++; } } } return count; }}Complexity
Time
O(N^2), where N is the length of the `hours` array. The nested loops result in checking approximately N^2 / 2 pairs.
Space
O(1), as we only use a constant amount of extra space for the counter and loop indices.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra memory, making it space-efficient.
Cons
Highly inefficient for large inputs, leading to a Time Limit Exceeded (TLE) error on most platforms.
The time complexity of O(N^2) makes it impractical for the given constraints (N up to 5 * 10^5).
A more efficient approach leverages the properties of modular arithmetic. The condition (hours[i] + hours[j]) % 24 == 0 is equivalent to (hours[i] % 24 + hours[j] % 24) % 24 == 0. This means we only need to consider the remainders of the hours when divided by 24. We can use a frequency map (an array of size 24) to store the counts of remainders encountered so far. By iterating through the array once, we can find the number of valid pairs in linear time.
Algorithm
- Initialize a
longcountercountto 0. - Create an integer array
remainderCountsof size 24, initialized to all zeros. This array will act as a frequency map for remainders. - Iterate through each
hourin the inputhoursarray. - For each
hour, calculate its remainder:rem = hour % 24. - Determine the complement remainder needed to make a sum divisible by 24:
complement = (24 - rem) % 24. - Add the number of times we have already seen the
complementremainder to ourcount. This is the value atremainderCounts[complement]. - Increment the frequency of the current
remin the map:remainderCounts[rem]++. - After iterating through all the hours, return the final
count.
Walkthrough
The core idea is to process the hours array in a single pass. As we iterate through each element h, we calculate its remainder rem = h % 24. For this rem, we need to find a previously seen element whose remainder complement_rem satisfies (rem + complement_rem) % 24 == 0. This complement_rem is (24 - rem) % 24.
We use an array remainderCounts of size 24 to keep track of the frequency of each remainder we've seen so far. For the current hour with remainder rem, we look up remainderCounts[complement_rem] to find how many numbers we've already processed that can form a complete day pair with the current number. We add this count to our total. After that, we update the frequency map by incrementing the count for the current remainder, remainderCounts[rem], making it available for subsequent elements.
class Solution { public long countCompleteDayPairs(int[] hours) { long count = 0; int[] remainderCounts = new int[24]; for (int hour : hours) { int rem = hour % 24; int complementRem = (24 - rem) % 24; count += remainderCounts[complementRem]; remainderCounts[rem]++; } return count; }}Complexity
Time
O(N), where N is the length of the `hours` array. We iterate through the array only once, and each operation inside the loop (modulo, array lookup, and increment) takes constant time.
Space
O(1). We use an array of a fixed size (24) to store remainder frequencies. The space requirement is constant and does not scale with the input size N.
Trade-offs
Pros
Extremely efficient with a linear time complexity of O(N).
Easily handles large inputs within typical time limits.
The logic is elegant and relies on a common pattern for pair-counting problems.
Cons
Requires extra space for the frequency map, although in this case, the space is constant (O(1)) and does not depend on the input size.
Solutions
Solution
class Solution {public long countCompleteDayPairs(int[] hours) { int[] cnt = new int[24]; long ans = 0; for (int x : hours) { ans += cnt[(24 - x % 24) % 24]; ++cnt[x % 24]; } return ans; }}class Solution {public: long long countCompleteDayPairs(vector<int> &hours) { int cnt[24]{}; long long ans = 0; for (int x : hours) { ans += cnt[(24 - x % 24) % 24]; ++cnt[x % 24]; } return ans; }};class Solution: def countCompleteDayPairs(self, hours: List[int]) -> int: cnt = Counter() ans = 0 for x in hours: ans += cnt[(24 - (x % 24)) % 24] cnt[x % 24] += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.