Count Pairs That Form a Complete Day I
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This is the most straightforward approach. It involves iterating through every possible unique pair of indices (i, j) where i < j and checking if the sum of the hours at these indices is a multiple of 24. If it is, a counter is incremented.
Algorithm
- Initialize a counter variable
countto 0. - Get the length of the
hoursarray,n. - Use a nested loop:
- The outer loop iterates from
i = 0ton - 2. - The inner loop iterates from
j = i + 1ton - 1.
- The outer loop iterates from
- Inside the inner loop, calculate the sum
hours[i] + hours[j]. - Check if
(hours[i] + hours[j]) % 24 == 0. - If the condition is true, increment
count. - After the loops complete, return
count.
Walkthrough
The algorithm uses two nested loops to generate all pairs of elements from the hours array. The outer loop picks the first element of the pair, and the inner loop picks the second element, ensuring that the second element's index is always greater than the first's to avoid duplicate pairs and self-pairing.
For each pair (hours[i], hours[j]), we calculate their sum. Then, we use the modulo operator (%) to check if this sum is perfectly divisible by 24. If (hours[i] + hours[j]) % 24 equals 0, it means the pair forms a complete day, and we increment our pair counter. After checking all possible pairs, the final value of the counter is the result.
class Solution { public int countCompleteDayPairs(int[] hours) { int 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. This is because for each element, we iterate through the rest of the array, leading to a quadratic number of operations.
Space
O(1), as it only requires a few variables to store the count and loop indices, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space.
Cons
Inefficient for large inputs due to its O(n^2) time complexity.
May result in a 'Time Limit Exceeded' error on coding platforms with larger constraints.
A more efficient approach utilizes modular arithmetic. The condition (a + b) % 24 == 0 is equivalent to (a % 24 + b % 24) % 24 == 0. We can iterate through the array once, using a frequency map (an array of size 24) to keep track of the remainders of the numbers encountered so far. For each number, we find how many previous numbers have the complementary remainder needed to sum up to a multiple of 24.
Algorithm
- Initialize a counter
countto 0. - Initialize a frequency array
remainderCountsof size 24 to all zeros. This array will store the counts of numbers seen so far for each possible remainder (0-23). - Iterate through each
hourin thehoursarray:- Calculate the remainder of the current hour:
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 iscount += remainderCounts[complement]. - Increment the frequency of the current remainder
remin theremainderCountsarray:remainderCounts[rem]++.
- Calculate the remainder of the current hour:
- After iterating through all the hours, return the total
count.
Walkthrough
The key insight is that we only care about the remainder of each hour when divided by 24. For an hour h, its remainder is rem = h % 24. To form a complete day with another hour h', its remainder rem' must satisfy (rem + rem') % 24 == 0. This means rem' must be (24 - rem) % 24.
We can iterate through the hours array from left to right, maintaining a frequency count of the remainders we've seen. An integer array of size 24 is perfect for this. For each hour in the input array:
- We calculate its remainder,
rem. - We find the required complement remainder,
complement. - We look up how many times we've already seen this
complementin our frequency array and add that number to our total pair count. This is because the currenthourcan form a valid pair with each of those previously seen numbers. - Finally, we update the frequency array by incrementing the count for the current
rem.
This single-pass approach avoids the nested loops and significantly improves performance.
class Solution { public int countCompleteDayPairs(int[] hours) { int count = 0; int[] remainderCounts = new int[24]; for (int hour : hours) { int rem = hour % 24; int complement = (24 - rem) % 24; count += remainderCounts[complement]; remainderCounts[rem]++; } return count; }}Complexity
Time
O(n), where n is the length of the `hours` array. We only need to iterate through the array once.
Space
O(1), because the frequency map is an array of a fixed size (24), its space requirement does not grow with the size of the input array.
Trade-offs
Pros
Highly efficient with a linear time complexity.
Optimal solution for the given problem constraints.
Cons
Slightly more complex to understand than the brute-force method.
Requires extra space for the frequency map, although it is constant.
Solutions
Solution
class Solution {public int countCompleteDayPairs(int[] hours) { int[] cnt = new int[24]; int 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 ansclass Solution {public: int countCompleteDayPairs(vector<int> &hours) { int cnt[24]{}; int ans = 0; for (int x : hours) { ans += cnt[(24 - x % 24) % 24]; ++cnt[x % 24]; } return ans; }};Video 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.