Count Pairs That Form a Complete Day I

Count Pairs That Form a Complete Day I

What is this problem about?

The "Count Pairs That Form a Complete Day I interview question" is a modular arithmetic challenge. You are given an array of integers representing hours. You need to find the number of pairs $(i, j)$ such that $i < j$ and the sum of hours[i] and hours[j] is a multiple of 24. A sum that is a multiple of 24 represents a full set of days (no leftover hours).

Why is this asked in interviews?

Companies like Infosys and Google use the "Count Pairs That Form a Complete Day coding problem" to test basic understanding of the modulo operator and "Hash Table interview pattern" optimization. While it can be solved with a simple nested loop, it serves as a foundation for more complex frequency-based counting problems.

Algorithmic pattern used

This problem can be solved using Simulation or Frequency Counting.

1. Brute Force ($O(N^2)$): Use two nested loops to check every pair $(i, j)$. If (hours[i] + hours[j]) % 24 == 0, increment the counter.
2. Optimized ($O(N)$):
   • Calculate the remainder of each hour when divided by 24.
   • Use an array of size 24 to store the frequency of each remainder.
   • For a remainder $r$, the complement needed to reach a multiple of 24 is $(24 - r) \% 24$.
   • The number of pairs is the sum of count[r] * count[complement] for all $r$, with special handling for $r=0$ and $r=12$ (where complement equals $r$).

Example explanation

Hours: [12, 12, 30, 18]

• 12 % 24 = 12.
• 12 % 24 = 12.
• 30 % 24 = 6.
• 18 % 24 = 18.
• Pair (12, 12): Sum = 24 (Multiple of 24).
• Pair (30, 18): Sum = 48 (Multiple of 24). Total pairs: 2.

Common mistakes candidates make

• Integer Overflow: Although not an issue for small arrays, summing hours before applying modulo can lead to overflow if values are extremely large.
• Deduplication: Counting the same pair twice or forgetting to handle the $i < j$ constraint.
• Modulo 24: Forgetting that if a remainder is 0, its complement is also 0, not 24.

Interview preparation tip

Always look for ways to use "Frequency Counting" when a problem involves finding pairs that sum to a constant $K$. This "Math interview pattern" is much more efficient than nested loops.