# Count Pairs That Form a Complete Day I
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-pairs-that-form-a-complete-day-i)
Canonical: https://scaleengineer.com/dsa/problems/count-pairs-that-form-a-complete-day-i
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
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`

# Approaches
## Brute Force Approach
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a counter variable `count` to 0.
- Get the length of the `hours` array, `n`.
- Use a nested loop:
  - The outer loop iterates from `i = 0` to `n - 2`.
  - The inner loop iterates from `j = i + 1` to `n - 1`.
- 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`.

## Optimized Approach using a Frequency Map
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.
**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.
**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.
### Explanation
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:
1. We calculate its remainder, `rem`.
2. We find the required complement remainder, `complement`.
3. We look up how many times we've already seen this `complement` in our frequency array and add that number to our total pair count. This is because the current `hour` can form a valid pair with each of those previously seen numbers.
4. 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.

```java
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;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Initialize a frequency array `remainderCounts` of 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 `hour` in the `hours` array:
  - 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 `complement` remainder to our `count`. This is `count += remainderCounts[complement]`.
  - Increment the frequency of the current remainder `rem` in the `remainderCounts` array: `remainderCounts[rem]++`.
- After iterating through all the hours, return the total `count`.

# Solutions
### Java

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

```

### Python

```python
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

```

### CPP

```cpp
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;
  }
};

```