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).
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; }}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.