# Count Pairs That Form a Complete Day II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-pairs-that-form-a-complete-day-ii)
Canonical: https://scaleengineer.com/dsa/problems/count-pairs-that-form-a-complete-day-ii
**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 <= 5 * 105`
* `1 <= hours[i] <= 109`

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

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

## Optimized Approach using a Frequency Map
A more efficient approach leverages the properties of modular arithmetic. The condition `(hours[i] + hours[j]) % 24 == 0` is equivalent to `(hours[i] % 24 + hours[j] % 24) % 24 == 0`. This means we only need to consider the remainders of the hours when divided by 24. We can use a frequency map (an array of size 24) to store the counts of remainders encountered so far. By iterating through the array once, we can find the number of valid pairs in linear time.
**Time:** O(N), where N is the length of the `hours` array. We iterate through the array only once, and each operation inside the loop (modulo, array lookup, and increment) takes constant time. · **Space:** O(1). We use an array of a fixed size (24) to store remainder frequencies. The space requirement is constant and does not scale with the input size N.
**Pros:** Extremely efficient with a linear time complexity of O(N).; Easily handles large inputs within typical time limits.; The logic is elegant and relies on a common pattern for pair-counting problems.
**Cons:** Requires extra space for the frequency map, although in this case, the space is constant (O(1)) and does not depend on the input size.
### Explanation
The core idea is to process the `hours` array in a single pass. As we iterate through each element `h`, we calculate its remainder `rem = h % 24`. For this `rem`, we need to find a previously seen element whose remainder `complement_rem` satisfies `(rem + complement_rem) % 24 == 0`. This `complement_rem` is `(24 - rem) % 24`.

We use an array `remainderCounts` of size 24 to keep track of the frequency of each remainder we've seen so far. For the current `hour` with remainder `rem`, we look up `remainderCounts[complement_rem]` to find how many numbers we've already processed that can form a complete day pair with the current number. We add this count to our total. After that, we update the frequency map by incrementing the count for the current remainder, `remainderCounts[rem]`, making it available for subsequent elements.

```java
class Solution {
    public long countCompleteDayPairs(int[] hours) {
        long count = 0;
        int[] remainderCounts = new int[24];
        
        for (int hour : hours) {
            int rem = hour % 24;
            int complementRem = (24 - rem) % 24;
            count += remainderCounts[complementRem];
            remainderCounts[rem]++;
        }
        
        return count;
    }
}
```
### Algorithm
- Initialize a `long` counter `count` to 0.
- Create an integer array `remainderCounts` of size 24, initialized to all zeros. This array will act as a frequency map for remainders.
- Iterate through each `hour` in the input `hours` array.
- For each `hour`, calculate its remainder: `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 the value at `remainderCounts[complement]`.
- Increment the frequency of the current `rem` in the map: `remainderCounts[rem]++`.
- After iterating through all the hours, return the final `count`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  long long countCompleteDayPairs(vector<int> &hours) {
    int cnt[24]{};
    long long 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

```