Welcome to Subscribe On Youtube

3185. Count Pairs That Form a Complete Day II

Description

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

Solutions

Solution 1: Counting

We can use a hash table or an array $\text{cnt}$ of length $24$ to record the occurrence count of each hour modulo $24$.

Iterate through the array $\text{hours}$. For each hour $x$, we can find the number that, when added to $x$, results in a multiple of $24$, and after modulo $24$, this number is $(24 - x \bmod 24) \bmod 24$. We then accumulate the occurrence count of this number from the hash table or array. After that, we increment the occurrence count of $x$ modulo $24$ by one.

After iterating through the array $\text{hours}$, we can obtain the number of index pairs that meet the problem requirements.

The time complexity is $O(n)$, where $n$ is the length of the array $\text{hours}$. The space complexity is $O(C)$, where $C=24$.

  • 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;
        }
    }
    
  • 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;
        }
    };
    
  • 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
    
    
  • func countCompleteDayPairs(hours []int) (ans int64) {
    	cnt := [24]int{}
    	for _, x := range hours {
    		ans += int64(cnt[(24-x%24)%24])
    		cnt[x%24]++
    	}
    	return
    }
    
  • function countCompleteDayPairs(hours: number[]): number {
        const cnt: number[] = Array(24).fill(0);
        let ans: number = 0;
        for (const x of hours) {
            ans += cnt[(24 - (x % 24)) % 24];
            ++cnt[x % 24];
        }
        return ans;
    }
    
    

All Problems

All Solutions