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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7

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 * 10^5
  • 1 <= hours[i] <= 10^9

Solution

Method 1 – Remainder Counting (Hash Map)

Intuition

If (hours[i] + hours[j]) is a multiple of 24, then (hours[i] % 24 + hours[j] % 24) % 24 == 0. We can count the frequency of each remainder and for each hour, count how many previous hours can pair with it to form a complete day. This is similar to the I version, but needs to be efficient for large n.

Approach

  1. Initialize an array of size 24 to count the frequency of each remainder modulo 24.
  2. For each hour in the array:
    1. Compute its remainder r = hour % 24.
    2. The complement remainder needed is (24 - r) % 24.
    3. Add the count of the complement to the answer.
    4. Increment the count of r in the array.
  3. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    long long countPairs(vector<int>& hours) {
        vector<long long> cnt(24, 0);
        long long ans = 0;
        for (int h : hours) {
            int r = h % 24;
            int comp = (24 - r) % 24;
            ans += cnt[comp];
            cnt[r]++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func countPairs(hours []int) int64 {
    cnt := make([]int64, 24)
    var ans int64
    for _, h := range hours {
        r := h % 24
        comp := (24 - r) % 24
        ans += cnt[comp]
        cnt[r]++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public long countPairs(int[] hours) {
        long[] cnt = new long[24];
        long ans = 0;
        for (int h : hours) {
            int r = h % 24;
            int comp = (24 - r) % 24;
            ans += cnt[comp];
            cnt[r]++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    fun countPairs(hours: IntArray): Long {
        val cnt = LongArray(24)
        var ans = 0L
        for (h in hours) {
            val r = h % 24
            val comp = (24 - r) % 24
            ans += cnt[comp]
            cnt[r]++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def countPairs(self, hours: list[int]) -> int:
        cnt = [0] * 24
        ans = 0
        for h in hours:
            r = h % 24
            comp = (24 - r) % 24
            ans += cnt[comp]
            cnt[r] += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn count_pairs(hours: Vec<i32>) -> i64 {
        let mut cnt = [0i64; 24];
        let mut ans = 0i64;
        for h in hours {
            let r = (h % 24) as usize;
            let comp = (24 - r) % 24;
            ans += cnt[comp];
            cnt[r] += 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    countPairs(hours: number[]): number {
        const cnt = Array(24).fill(0);
        let ans = 0;
        for (const h of hours) {
            const r = h % 24;
            const comp = (24 - r) % 24;
            ans += cnt[comp];
            cnt[r]++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of hours, since we process each hour once.
  • 🧺 Space complexity: O(1), since the remainder count array is always of size 24.