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