3184. Count Pairs That Form a Complete Day I
Description
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 <= 100
1 <= hours[i] <= 109
Solutions
Solution 1: Counting
We can use a hash table or an array $\textit{cnt}$ of length $24$ to record the occurrence count of each hour modulo $24$.
Iterate through the array $\textit{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 $\textit{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 $\textit{hours}$. The space complexity is $O(C)$, where $C=24$.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 |
|