Count Pairs That Form a Complete Day II

Count Pairs That Form a Complete Day II

What is this problem about?

The "Count Pairs That Form a Complete Day II interview question" is the scaled-up version of the "Complete Day" problem. You are given an array of hours and need to count pairs $(i, j)$ where (hours[i] + hours[j]) % 24 == 0. However, the constraints on the array size are much larger, making an $O(N^2)$ brute-force solution impossible. You must use a linear-time approach.

Why is this asked in interviews?

Companies like Microsoft and Google ask the "Count Pairs That Form a Complete Day II coding problem" to verify if a candidate can optimize an algorithm from quadratic to linear time. It evaluates mastery of modular arithmetic and the ability to use an auxiliary data structure (like a frequency array) to achieve $O(N)$ performance.

Algorithmic pattern used

This problem follows the Frequency Counting with Modulo pattern.

1. Map Remainders: Use an array freq of size 24 to count the occurrences of each remainder hours[i] % 24.
2. Complement Search: For each number in the input, calculate its remainder $r$. The number of existing elements that can form a full day with it is freq[(24 - r) % 24].
3. Update Total: Add that count to your result and then increment freq[r] for future elements. This single-pass approach ensures that each pair is counted exactly once and the time complexity is $O(N)$.

Example explanation

Hours: [12, 12, 24]

1. First 12: Remainder 12. Complement $(24-12)\%24 = 12$. freq[12] is 0. count = 0. freq[12] = 1.
2. Second 12: Remainder 12. Complement 12. freq[12] is 1. count = 1. freq[12] = 2.
3. 24: Remainder 0. Complement $(24-0)\%24 = 0$. freq[0] is 0. count = 1. freq[0] = 1. Total pairs: 1.

Common mistakes candidates make

• Slow Data Structure: Using a full Hash Map when a fixed-size array of 24 is much faster.
• Handling Zero: Failing to realize that the complement of remainder 0 is 0 itself. The formula (24 - r) % 24 handles this correctly.
• Integer Types: Forgetting that the final count of pairs can exceed $2^{31} - 1$ for large $N$, requiring a 64-bit integer (long).

Interview preparation tip

Practice "Complement Counting." This "Array interview pattern" is the standard solution for "Two Sum" style problems. If the target sum is a multiple of $K$, always group by remainders modulo $K$.