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 <= 1001 <= 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$.
Python3
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 ans
Java
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;
}
}
C++
class 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;
}
};
Go
func countCompleteDayPairs(hours []int) (ans int) {
cnt := [24]int{}
for _, x := range hours {
ans += cnt[(24-x%24)%24]
cnt[x%24]++
}
return
}
TypeScript
function countCompleteDayPairs(hours: number[]): number {
const cnt: number[] = Array(24).fill(0);
let ans: number = 0;
for (const x of hours) {
ans += cnt[(24 - (x % 24)) % 24];
++cnt[x % 24];
}
return ans;
}